本文共 3459 字，大约阅读时间需要 11 分钟。

图

1.图简述

• 图由顶点(vertex)和边(edge)组成，通常表示为G=(V,E)
• G表示一个图，V是顶点集，E是边集；
• 顶点集V有穷且非空；
• 任意两个顶点之间都可以用边来表示它们之间的关系，边集E可以是空的；

2.应用举例

图结构的应用极其广泛:

• 社交网络
• 地图导航
• 游戏开发

3.图的一些相关概念

3.1 有向图

有向图的边是有明确方向的；

有向无环图：如果一个有向图，从任意顶点出发无法经过若干条边回到该顶点，那么它就是一个有向无环图。

3.2 出度和入度

出度 入度适用于有向图；

出度(out-degree):

• 如果一个顶点的出度为x，是指有x条边以该顶点为起点

入度(in-degree):

• 如果一个顶点的入度为x，是指有x条边以该顶点为终点

3.3 无向图

无向图的边是无方向的；

3.4 无向完全图

无向完全图的任意两个顶点之间都存在边；

n个顶点的无向完全图由n(n-1)/2条边；即(n-1) + (n-2) + (n-3) + … + 3 + 2 + 1

3.5 有向完全图

有向完全图的任意两个顶点之间都存在方向相反的两条边；

n个顶点的有向完全图有n(n-1)条边；

• 稠密图(Dense Graph):边数接近于或等于完全图；
• 稀疏图(Sparse Graph)：边数远远少于完全图；

3.6 有权图

有权图的边可以拥有权值。

3.7 连通图

• 如果顶点x和y之间存在可相互抵达的路径(直接或间接的路径)，则称x和y是连通的；

3.8 连通分量

• 连通分量：无向图的极大连通子图
• 连通图只有一个连通分量，即其本身；非连通的无向图有多个连通分量；
• 举例：下面的无向图有3个连通分量

3.9 强连通图

• 如果有向图G中任意两个顶点都是连通的，则称G为强连通图；

3.10 强联通分量

• 强连通分量：有向图的极大强连通子图
• 强连通图只有一个强连通分量，即其自身；非强梨连通的有向图有多个强连通分量；

4.图的实现

图有2种常见的实现方案：

• 邻接矩阵(Adjacency Matrix)
• 邻接表(Adjacency List)

4.1 邻接矩阵

邻接矩阵的存放方式：

• 一维数组存放顶点信息；
• 二维数组存放边信息；

4.2 邻接表

4.3 邻接表-有权图

5.图的遍历

从图中某一顶点出发访问图中其余顶点，且每一个顶点仅被访问一次；

图有2种常见的遍历方式(有向图、无向图都适用)；

• 广度优先搜索(BFS),又称为宽度优先搜索、横向优先搜索
• 深度优先搜索(DFSS)

5.1 广度优先搜索(BFS)

之前所学的二叉树层序遍历就是一种广度优先搜索

5.2 深度优先搜索(DFS)

之前学的二叉树前序遍历就是一种深度优先搜索

6.AOV网(Activity On Vertex Network)

• 一项大的工程常被分为多个小的子工程；

子工程之间可能存在一定的先后顺序，即某些子工程必须在其他的一些子工程完成后才能开始

• 在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，子工程被称为活动(Activity)
• 标准的AOV网必须是一个有向五环图

6.1 拓扑排序

• 将AOV网中所有活动排成一个序列，使得每个活动的前驱活动都排在该活动的前面。
• 比如上图的拓扑排序结果是A B C D E F

拓扑排序的算法流程：

• 假设L是存放拓扑排序结果的列表
  • 把所有入度为0的顶点放入L中，然后把这些顶点从图中去掉；
  • 重复上述操作，直到找不到入度为0的顶点
• 如果此时L中的元素个数和顶点个数总数相同，说明拓扑排序完成
• 如果此时L中的元素个数小于顶点总数，说明原图中存在环，无法进行拓扑排序

6.2 AOV有关的题目

Leetcode 课程表I

7 生成树

7.1 生成树

生成树，也称为支撑树

• 连通图的极小连通子图，它含有图中全部的n个顶点，恰好只有n-1条边；

7.2 最小生成树

最小生成树：

• 也被称为最小权重树
• 是所有生成树中，总权值最小的那树
• 适用于有权的连通图(无向)

最小生成树在许多领域都有重要的作用，例如

• 要在n个城市之间铺设光缆，使它们都可以通信；
• 铺设光缆的费用很高，且各个城市之间因为距离不同等因素，铺设光缆的费用也不同；
• 那么如何使铺设光缆的总费用最低？

7.3 求最小生成树

求最小生成树的2个经典算法：

• Prim(普利姆算法)
• Kurskal(克鲁斯克尔算法)

求最短路径算法

• Dijkstra(迪杰斯特拉算法)；
• Floyd(弗洛伊德算法)

• 最小生成树是用最小代价遍历整个图中所有顶点，所有的权值和最小；而最短路径只是保证出发点到终点的路径和最小，不一定要经过所有顶点。
• 最小生成树是一群点(所有点)的路径代价和最小，是一个n-1条边的数，最短路径是从一个点到另外一个点的最短路径；

7.3.1 Prim普利姆算法

从单一顶点开始，普利姆算法按照如下步骤逐步扩大树中所包含的顶点的数目，直到遍及连通图中的所有顶点

• 输入：一个加权连通图，其中顶点集合为V，边集合为E；
• 初始化：Vnew={x}， 其中x为集合V中的任一节点(起始点)，Enew={}；
• 重复以下操作，直到Vnew=V;
  • 在集合E中选取权值最小的边(u,v),其中u为集合Vnew中的元素，而v不是；
  • 将v加入集合Vnew中 ，将(u,v)加入集合Enew中
• 输出：使用集合Vnew和Enew来描述所得到的最小生成树；

7.3.2 Kruskal克鲁斯卡尔算法

Prim算法是以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树。同样的思路，也可以直接就以边来构建生成树也是很自然的想法，只不过 构建的时候要考虑是否会形成环路而已。

7.4 求A和B两点之间的最短路径

最短路径是指两顶点之间权值之和最小的路径(有向图、无向图均适用，不能有负权环)

求解最短路径的经典算法：

• 单源最短路径算法
  • Dijkstra(迪杰斯特拉算法)
• 多源最短路径算法
  • Floyd（弗洛伊德算法）

7.4.1 Dijkstra算法

Dijkstra属于单源最短路径算法，用于计算一个顶点到其它所有顶点的最短路径；

• 使用前提：不能有负权边；
• 时间复杂度：可优化至O(ElogV) E是边数量 V是节点数

Dijkstra-等价思考

Dijkstra的原理其实跟生活 中的一些自然现象完全一样：

• 把每一个顶点想象成一块小石头；
• 把每一条边想象成一条绳子，每一条绳子都连接着2块小石头，边的权值就是绳子的长度；
• 将小石头和绳子平放在一张桌子上
• 接下来想象一下，手拽着小石头A，慢慢地向上提起来，远离桌面
• B,D,C,E会依次离开桌面
• 最后绷直的绳子就是A到其他小石头的最短路径

Dijkstra算法步骤：

• 初始化时，S中只含有源节点；U为其他结点；计算S中的源节点到U中其他结点的路径；
• 之后从U中挑选一个距离最小的顶点k加入到S中；(该选定的距离就是v到k的最短路径长度)；
• 以k为新考虑的中间点，更新源节点v到顶点u的距离，若短则更新
• 重复步骤，直到所有顶点都包含在S中了。

7.4.2 Floyd算法

Floyd属于多源最短路径算法，能够求出任意两个顶点之间的最短路径

• 支持负权边；
• 时间复杂度为O(V^3) 效率比执行V次Dijkstra算法要好(V表示顶点数量)

算法原理：

• 从任意顶点i到任意顶点j的最短路径不外乎两种可能

  • 直接从i到j
  • 从i经过若干个顶点到j

• 假设dist(i,j)为顶点i到顶点j的最短路径的距离

• 对于每一个顶点k，检查dist(i,k)+dist(k,j)<dist(i,j)是否成立

  • 如果成立，证明i到k再到j的路径比i直接到j的路径短，设置dist(i,j)=dist(i,k)+dist(k,j)
  • 当我们遍历完所有结点k，dist(i,j)中记录的便是i到j的最短路径的距离

• 时间复杂度为O(V^3) 效率比执行V次Dijkstra算法要好(V表示顶点数量)

算法原理：

• 从任意顶点i到任意顶点j的最短路径不外乎两种可能

  • 直接从i到j
  • 从i经过若干个顶点到j

• 假设dist(i,j)为顶点i到顶点j的最短路径的距离

• 对于每一个顶点k，检查dist(i,k)+dist(k,j)<dist(i,j)是否成立

  • 如果成立，证明i到k再到j的路径比i直接到j的路径短，设置dist(i,j)=dist(i,k)+dist(k,j)
  • 当我们遍历完所有结点k，dist(i,j)中记录的便是i到j的最短路径的距离

  

转载地址：https://codingchaozhang.blog.csdn.net/article/details/115430479 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！