[数据结构与算法]【数据结构】第六章：图

第六章：图

一、基本概念

与图G相关的概念：

与顶点V相关的概念：

与边E相关的概念：

二、图的ADT

三、图的存储结构

图没有顺序存储结构，但是可以借助二维数组来表示元素之间的关系。

• 数组表示法（邻接矩阵）
• 链式表示法（邻接表、邻接多重表、十字链表）

1.数组表示法

建立一个顶点表（记录各个顶点的信息）和一个邻接矩阵（表示各个顶点之间边的关系）

设图A=(V, E)有n个顶点：

图的邻接矩阵是一个二维数组A.arcs[n][n]定义为：

（1）无向图邻接矩阵表示

1. 无向图的邻接矩阵是对称的
2. 顶点i的度 = 第i行/列中1的个数
3. 完全图的邻接矩阵中，对角元素为0其余全为1

（2）有向图邻接矩阵表示

有向图邻接矩阵表示：

1. 有向图的邻接矩阵可能是不对称的
2. 顶点的出度=第i行元素之和、顶点的入度=第i列元素之和’
3. 顶点的度=第i行元素之和+第i列元素之和

有向网邻接矩阵表示：

的邻接矩阵是一个二维数组A.arcs[n][n]定义为：

（3）邻接矩阵建立无向网

邻接矩阵的存储表示：用两个数组分别存储顶点表和邻接矩阵，

演示案例：采用邻接矩阵表示法创建无向网

1. 输入总顶点vexnum数和总边数arcnum
2. 建立顶点表：依次输入点的信息存入顶点表中
3. 初始化邻接矩阵，使每个权值初始化为极大值
4. 根据图G的边的情况构造邻接矩阵

（4）邻接矩阵表示法分析：

邻接矩阵的优点：

1. 直观、简单、易于理解
2. 便于检查任意一对顶点之间是否存在联系（边）
3. 便于找到任意顶点的所有邻接点（有联系的点）
4. 便于计算任意顶点的度：从该点出发的边数为出度、指向该点的边数为入度

邻接矩阵的缺点：

1. 不利于增加和删除顶点
2. 浪费空间—存储稀疏图，点很多而边很少有大量无效元素
3. 浪费时间—统计稀疏图中一共有多少条边

2.链式表示法

建立一个顶点表（记录各个顶点的信息）和一个线性链表（记录关联着同一顶点的边的信息/以顶点为尾的弧）

设图A=(V, E)有n个顶点：

（1）无向图邻接表表示

1. 邻接表不是唯一的（链表结点的顺序是可调换的）
2. 若无向图中有n个顶点与e条边，则邻接表需要n个头结点与2e个表结点来存储（适合稀疏矩阵的存储）
3. 无向图中顶点vi的度即为第i个单链表中的节点数

（2）有向图邻接表表示

1. 有向图中顶点vi的出度即为第i个单链表中的结点数
2. 有向图中顶点vi的入度即为整个单链表中的邻接点域值为i-1的结点数

（3）邻接表建立无向网

邻接表的存储表示：

演示案例：采用邻接表表示法创建无向网

1. 输入总顶点vexnum数和总边数arcnum
2. 建立顶点表：依次输入点的信息存入顶点表中，并且使每个表头结点的指针域初始化为NULL
3. 根据图G的边的情况构造邻接表（单链表）：
   1. 依次输入每条边依附的两个顶点，查找两个顶点的序号i和j建立边结点
   2. 将此边结点分别插入到vi和vj对应的两个边链表的头部

（4）邻接表表示法分析：

1. 节约稀疏图的空间：需要N个头指针+2E个结点（每个结点至少2个域）
2. 不便于检查任意一对顶点之间是否存在联系（边）
3. 便于找到任意顶点的所有邻接点（有联系的点）
4. 便于计算任意顶点的度：对于无向图方便，对于有向图只能计算出度，入度需要逆邻接表来计算

邻接矩阵与邻接表之间的对比：

3.链式表示法的改进：

（1）十字链表：

为了解决邻接表存储有向图时度计算困难的问题，（邻接表只便于求出度、逆邻接表只便于求入度）提出了十字链表：

十字链表，Orthogonal List是有向图的另一种链式存储结构，是将有向图的邻接表和逆邻接表结合起来形成的一种链表。

有向图中的弧对应十字链表中的弧结点，有向图中的顶点在十字链表中有对应的顶点结点。

案例演示：根据如下有向图建立十字链表

十字链表建立完毕

（2）邻接多重表：

为了解决邻接表存储无向图时每条边重复存储的问题，提出了邻接多重表：

案例演示：根据如下无向图建立邻接多重表

四、图的遍历

从已给连通图中的某一顶点出发，沿着一些边访问一遍图中的所有顶点，且使每个顶点仅被访问一次称作图的遍历。

注意：遍历的实质就是找到每一个顶点的邻接点的过程（需要避免重复访问问题—设置visit数组）

1.深度优先搜索DFS

（1）DFS思想：

1. 在访问图中起始顶点v之后，由顶点v出发访问它的任一邻接顶点w1
2. 在访问图中邻接顶点w1之后，由顶点w1出发访问它的任一邻接但是还没有被访问过的顶点w2
3. 在访问图中邻接顶点w2之后，进行类似的访问w3、w4、w5…直到所有的邻接顶点都被访问过为止
4. 当在某顶点时其所有邻接顶点都被访问过，退到上一个访问过的顶点检测其是否还有没有被访问过的邻接顶点（回溯）
   1. 如果有则对该未访问顶点进行访问，再从该顶点出发，进行类似的访问w3、w4、w5…直到所有的邻接顶点都被访问过为止
   2. 如果没有则再退到上一个访问过的顶点检测其是否还有没有被访问过的邻接顶点（继续回溯）
5. 重复上述过程，直到连通图中的所有顶点都被访问过为止。

注意：连通图的深度优先遍历类似于树的先根遍历

（2）DFS邻接矩阵上的实现：

根据邻接矩阵后的DFS访问顺序：v2、v1、v3、v5、v4、v6

注意：如果图的存储结构确定（此处邻接矩阵结构确定）时，则DFS遍历的顺序只有一种

注意：回溯的过程即为if不执行的情况，无需书写！

（3）算法分析：

• 用邻接矩阵来表示图，遍历图中的每一个顶点都要从头扫描该顶点所在的行，时间复杂度为O（n²）
• 用邻接表来表示图，虽然有2e个表结点但是只需扫描e个结点即可，加上访问n个头结点的时间，时间复杂度为O（n + e）

1. 稠密图适用于在邻接矩阵上进行DFS
2. 稀疏图适用于在邻接表上进行DFS

2.广度优先搜索BFS

（1）BFS思想：

1. 从图中某结点出发，首先依次访问该结点的所有相邻邻接结点vi1、vi2、…vin（同一层）
2. 再按照这些顶点被访问的先后次序，依次访问与它们相邻的所有未被访问的顶点
3. 重复此过程，直到所有顶点均被访问为止

注意：连通图的广度优先遍历类似于树的层次遍历

（2）BFS邻接表上的实现：

详细BFS过程如下：

算法实现：

（3）算法分析：

• 用邻接矩阵来表示图，BFS对于每一个被访问到的顶点，都要循环检测矩阵中的完整一行（n个元素），时间复杂度为O（n²）
• 用邻接表来表示图，虽然有2e个表结点但是只需扫描e个结点即可，加上访问n个头结点的时间，时间复杂度为O（n + e）

DFS与BFS算法效率比较：

1. 空间复杂度相同O（n）：DFS借用了栈，而BFS借用了队列
2. 时间复杂度只与存储结构（邻接表 or 邻接矩阵）有关，而与搜索的路径无关

五、图的应用

1.最小生成树

生成树：是指所有顶点均由边连接在一起，但不存在回路的图。

• 一个图可以有许多棵不同的生成树

所有生成树具有以下共同特点：

1. 生成树的顶点个数与图的顶点个数相同
2. 生成树是图的极小连通子图，去掉任意一条边则为非连通子图
3. 有n个顶点的连通图，其生成树有n-1条边（含有n个顶点n-1条边的图不一定是生成树）
4. 在生成树中再添加一条边必然形成回路
5. 生成树中任意两个顶点间的路径是唯一的

（1）ST：

生成树Spanning Tree如何生成？下面以无向图为例：

根据生成树的定义需要包含所有的顶点、且不存在回路，

可以直接对无向图进行遍历访问其所有的顶点，在访问的过程中将走过的边添加到生成树上，

（2）MST性质：

给定一个无向网，在该网络的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树/最小代价生成树。

注意：MST最小生成树性质实际上是一种贪心算法，即选择权值最小的边。

MST性质：

• 设N=(V, E)是一个连通网，且U是顶点集V的一个非空子集，
• 若边(u, v)是一条具有最小权值的边，其中u∈U、v属于V-U，则必存在一棵包含边(u, v)的最小生成树。

演示案例：

注意：大部分最小生成树算法都是利用MST的性质来构造最小生成树。

（3）Prim构造MST：

算法思想：

（4）Kruskal构造MST：

注意：生成的最小生成树可能不是唯一的

（5）Prim&Kruskal比较：

2.最短路径

在有向网中A点（起始点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径即最短路径。

补充：最短路径与最小生成树的不同在于，路径上不一定包含n个顶点，也不一定包含n-1条边（所有顶点与所有边）。

（1）Dijkstra算法：

单源最短路径问题可以使用Dijkstra迪杰斯特拉算法进行处理，Dijkstra迪杰斯特拉算法按照路径长度递增次序产生最短路径

1. 初始化：先找出从源点v₀到各终点vk的直达路径（v₀，v_k），即通过一条弧到达的路径

2. 路径选择：从初始化得到的路径中找出一条长度最短的路径（v₀，u）

3. 路径调整：在路径选择之后对其余各条路径进行适当的调整

   若在图中存在弧（u，v_k）且（v₀， u）+（u，v_k）<（v₀，v_k），则以路径（v₀，u，v_k）替代（v₀，v_k）

4. 递归：在调整后的各条路径中，再寻找长度最短的路径依次类推

（2）Floyd算法：

求所有顶点间最短路径可以使用Floyd弗洛伊德算法，逐个顶点试探从v_i到v_j的所有可能存在的路径中，选出一条长度最短的路径。

求最短路径步骤：

1. 初始时设置一个n阶方阵令其对角线元素为0（不考虑自身），若存在弧<v_i, v_j>则对应元素为权值，否则为正无穷
2. 逐步地在原直接路径中增加中间顶点，若加入中间顶点后路径变短则修改，否则维持原值。
3. 当所有顶点试探完毕之后，算法结束

3.拓扑排序&AOV网

注意：关于拓扑排序与关键路径的问题研究主要是针对于有向无环图的。

有向无环图，无环/回路的有向图简称DAG图（Directed Acycline Graph）

有向无环图常用来描述一个工程/系统的进行过程，一个工程可以分为若干个子工程。

（1）AOV网：

用一个有向图表示工程的各子工程及其相互制约的关系，

以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网AOV（Activity On Vertex network）

（2）拓扑排序：

在AOV网没有回路的前提下，将全部活动排成一个线性序列，

使得若AOV网中有弧<i, j>存在，则在这个序列中i一定排在j的前面，具有这种性质的线性序列称为拓扑有序序列，

相应的拓扑有序排序的算法称为拓扑排序。

拓扑排序方法：

1. 在有向图中选一个没有前驱的顶点并且对其进行输出
2. 从图中删除该顶点和所有以其为尾的弧
3. 重复上述步骤直至全部顶点均已输出

检测AOV网中是否存在环：

对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在其拓扑有序序列中，则该AOV网必定不存在环。

4.关键路径&AOE网：

（1）AOE网：

用一个有向图表示工程的各子工程及其相互制约的关系，

以弧表示活动，顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网AOE（Activity On Edge）

（2）关键路径：

4个相关概念：

• 关键活动：关键路径上的活动，即l(i) - e(i) = 0 的活动
• 关键路径：路径长度最长的路径，由许多个关键活动组成

关键路径的求解步骤：

关键路径的几点注意事项：

1. 若网中有几条个关键路径，则需要加快同时在几条关键路径上的关键活动，如a11、a10、a8、a7

   

2. 如果一个活动处于所有的关键路径上，那么提高这个活动的速度就能缩短整个工程的完成时间，如a1、a4

3. 处于所有的关键路径上的活动完成的时间不能缩短太多，否则原来的关键路径可能会改变（需要重写寻找关键路径）