数据结构-第六章

字数统计: 451字   |   阅读时长≈ 1分

数据结构

第六章 图

author:slightwjq
2023年1月23日

6.1 图的基本概念

图的定义

  • 有向图：有向边和顶点的集合
  • 无向图：无向边和顶点的集合
  • 简单图：不存在重复边，不存在顶点到自身的边
  • 完全图：任意两个顶点之间都有边
  • 子图：图的一部分
  • 连通图：无向图中，任意两个顶点之间有路径存在
  • 强连通图：有向图中，任意两个顶点之间都有相互的路径
  • 生成树：包含图中全部顶点的一个极小连通子图

6.2 图的存储及基本操作

邻接矩阵存储：用一个一个一位数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间邻接关系的二维数组称为邻接矩阵。
邻接表法：对图中每个顶点形成一个单链表，存储该点和其余有边的顶点的关系。
十字链表法：
多重合邻接表：

6.3 图的遍历

广度优先搜索：不是一个递归算法，必须借助辅助队列。可以用于求单源最短路径问题。
深度优先搜索：是递归算法，需要借助一个工作栈。

6.4 图的应用

最小生成树

Prim算法：每次取邻近的最短边，时间复杂度是O(V^2^)。
Kruskal算法：每次都选取整体最小但是未加入集合的最短边，时间复杂度是O(ElogE)。

最短路径

迪杰斯特拉Dijkstra算法，求单源最短路径，基于贪心策略。
弗洛伊德Floyd算法：求所有顶点的最短路径。

拓扑排序

略，但很重要！！！

关键路径

略，但很重要！！！

赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

还在学习中的在读硕士，网站可能有些连接暂无法正常使用，有问题可以联系QQ:2863826649