4.图的应用

最小生成树

一个连通图的生成树包含图的所有顶点,并且只含尽可能少的边。对于生成树来说,若砍去它的一条边,则会使生成树变成非连通图:若给它增加一条边,则会形成图中的一条回路。

对于一个带权连通无向图 $G=(V, E)$, 生成树不同, 每棵树的权 (即树中所有边上的权值之 和）也可能不同。设 $\Re$ 为 $G$ 的所有生成树的集合, 若 $T$ 为 $\Re$ 中边的权值之和最小的那棵生成树, 则 $T$ 称为 $G$ 的最小生成树 (Minimum-Spanning-Tree, MST)。

最小生成树的性质

1. 最小生成树不是唯一的,即最小生成树的树形不唯一,只中可能有多个最小生成树。当图$G$ 中的各边权值互不相等时, $G$ 的最小生成树是唯一的; 若无向连通图 $G$ 的边数比顶点 数少 1 , 即 $G$ 本身是一棵树时, 则 $G$ 的最小生成树就是它本身。
2. 最小生成树的边的权值之和总是唯一的, 虽然最小生成树不唯一, 但其对应的边的权值 之和总是唯一的, 而且是最小的。
3. 最小生成树的边数为顶点数减 1 。

6.4.1最小生成树

---

00:01

【课件】6.4.1最小生成树

---

构造最小生成树有多种算法, 但大多数算法都利用了最小生成树的下列性质:

假设 $G=(V, E)$ 是一个带权连通无向图, $U$ 是顶点集 $V$ 的一个非空子集。若 $(u, v)$ 是一条具有最小权值的边, 其中 $u \in U, v \in V-U$, 则必存在一棵包含边 $(u, v)$ 的最小生成树。

prim算法

6.4.1最小生成树 -prim算法

---

03:36

image.png

从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

时间复杂度$O(\mid V^2\mid)$,适用于求解边稠密的图的最小生成树

prime算法核心

image.png

Kruskal算法

6.4.1最小生成树 -Kruskal 算法

---

07:47

image.png

每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选)直到所有结点都连通

通常在 Kruskal 算法中, 采用堆 (见第 7 章) 来存放边的集合, 因此每次选择最小权值的边 只需$O\left(\log _{2}|E|\right)$ 的时间。此外, 由于生成树 $T$ 中的所有边可视为一个等价类, 因此每次添加新的边 的过程类似于求解等价类的过程, 由此可以采用并查集的数据结构来描述 $T$, 从而构造 $T$ 的时间复杂度为 $O\left(|E| \log _{2}|E|\right)$ 。因此, Kruskal 算法适合于边稀疏而顶点较多的图。

kruskal算法核心

image.png

最短路径

求解最短路径的算法通常都依赖于一种性质，即两点之间的最短路径也包含了路径上其他顶点间的最短路径。带权有向图G的最短路径问题一般可分为两类：

1. 一是单源最短路径，即求图中某一顶点到其他各顶点的最短路径，可通过经典的 Dikstra（迪杰斯特拉）算法求解;
2. 二是求每对顶点间的最短路径，可通过 Floyd（弗洛伊德）算法来求解。

BFS求无权图单源最短路径

6.4.2_1最短路径问题_BFS算法

---

00:01

BFS求无权图单元最短路径算法实现

定义了三个数组visited：当前结点是否已经被访问过、p：从出发结点到当前结点的路径，path：求的单源最短路径，所以需要记录从出发结点到当前结点的路径，path记录的就是到达当前结点的上一个结点。

下图是从2号顶点出发

image.png

Dikstra 算法求单源最短路径问题

6.4.2_2最短路径问题_Dijkstra算法

---

00:08

6.4.2_2最短路径问题_Dijkstra算法

---

03:16-过程

6.4.2_2最短路径问题_Dijkstra算法

---

11:56-时间复杂度

算法执行过程

image.png

1. 初始化: 集合 $S$ 初始为 $\left\{v_{1}\right\}, v_{1}$ 可达 $v_{2}$ 和 $v_{5}, v_{1}$ 不可达 $v_{3}$ 和 $v_{4}$, 因此 dist [] 数组各元素的 初值依次设置为 $\operatorname{dist}[2]=10, \operatorname{dist}[3]=\infty, \operatorname{dist}[4]=\infty$, dist [5]=5。
2. 第一轮: 选出最小值 dist [5], 将顶点 $v_{5}$ 并入集合 $S$, 即此时已找到 $v_{1}$ 到 $v_{5}$ 的最短路径。 当 $v_{5}$ 加入 $S$ 后, 从 $v_{1}$ 到集合 $V-S$ 中可达顶点的最短路径长度可能会产生变化。因此需要更新 dist [] 数组。 $v_{5}$ 可达 $v_{2}$, 因 $v_{1} \rightarrow v_{5} \rightarrow v_{2}$ 的距离 8 比 dist [2]=10 小, 更新 dist [2] =8; $v_{5}$ 可达 $v_{3}, v_{1} \rightarrow v_{5} \rightarrow v_{3}$ 的距离 14, 更新 dist [3] =14; $v_{5}$ 可达 $v_{4}, v_{1} \rightarrow v_{5} \rightarrow v_{4}$ 的距离 7, 更新 dist [4] $=7$ 。
3. 第二轮: 选出最小值 dist [4], 将顶点 $v_{4}$ 并入集合 $S$ 。继续更新 dist [] 数组。 $v_{4}$ 不可达
   $v_{2}, \operatorname{dist}[2]$ 不变; $v_{4}$ 可达 $v_{3}, v_{1} \rightarrow v_{5} \rightarrow v_{4} \rightarrow v_{3}$ 的距离 13 比 dist [3] 小, 故更新 dist [3] =13。
4. 第三轮: 选出最小值 dist [2], 将顶点 $v_{2}$ 并入集合 $S$ 。继续更新 dist [ ] 数组。 $v_{2}$ 可达 $v_{3}$, $v_{1} \rightarrow v_{5} \rightarrow v_{2} \rightarrow v_{3}$ 的距离 9 比 dist [3] 小, 更新 dist [3] = 9 。
5. 第四轮: 选出唯一最小值 dist [3], 将顶点 $v_{3}$ 并入集合 $S$, 此时全部顶点都已包含在 $S$ 中。

时间复杂度$O(\mid V^2\mid)$
Dijkstra 算法不适用于有负权值的带权图

Floyd算法

求出每一对顶点之间的最短路径

6.4.2_3最短路径问题_Floyd算法

---

00:00

【课件】6.4.2_3最短路径问题_Floyd算法

---

6.4.2_3最短路径问题_Floyd算法

---

12:38-更复杂的实例

定义一个 ${n}$ 阶方阵序列 ${A^{(-1)}, A^{(0)}, \cdots, A^{(n-1)}}$, 其中,

$$\begin{array}{c} A^{(-1)}[i][j]=\operatorname{arcs}[i][j] \\ A^{(k)}[i][j]=\operatorname{Min}\left\{A^{(k-1)}[i][j], \quad A^{(k-1)}[i][k]+A^{(k-1)}[k][j]\right\}, \quad k=0,1, \cdots, n-1 \end{array}$$

式中, ${A^{(0)}[i][j]}$ 是从顶点 ${v_{i}}$ 到 ${v_{j}}$ 、中间顶点是 ${v_{0}}$ 的最短路径的长度, ${A^{(k)}[i][j]}$ 是从顶点 ${v_{i}}$ 到 ${v_{j}}$ 、中间顶点的序号不大于 ${k}$ 的最短路径的长度。Floyd 算法是一个迭代的过程, 每迭代一次, 在从 到 ${v_{j}}$ 的最短路径上就多考虑了一个顶点; 经过 ${n}$ 次迭代后, 所得到的 ${A^{(n-1)}[i][j]}$ 就是 ${v_{i}}$ 到 ${v_{j}}$ 的最短 路径长度, 即方阵 ${A^{(n-1)}}$ 中就保存了任意一对顶点之间的最短路径长度。

算法执行过程

image.png

1. 初始化: 方阵 $A^{(-1)}[i][j]=\operatorname{arcs}[i][j]$ 。
2. 第一轮: 将 $v_{0}$ 作为中间顶点, 对于所有顶点对 $\{i, j\}$, 如果有 $A^{-1}[i][j]>A^{-1}[i][0]+A^{-1}[0][j]$, 则将 $A^{-1}[i][j]$ 更新为 $A^{-1}[i][0]+A^{-1}[0][j]$ 。有 $A^{-1}[2][1]>A^{-1}[2][0]+A^{-1}[0][1]=11$, 更新 $A^{-1}[2][1]=11$, 更新后的方阵标记为 $A^{0}$ 。
3. 第二轮: 将 $v_{1}$ 作为中间顶点, 继续检测全部顶点对 $\{i, j\}$ 。有 $A^{0}[0][2]>A^{0}[0][1]+A^{0}[1][2]=10$, 更新 $A^{0}[0][2]=10$, 更新后的方阵标记为 $A^{1}$ 。
4. 第三轮: 将 $v_{2}$ 作为中间顶点, 继续检测全部顶点对 $\{i, j\}$ 。有 $A^{1}[1][0]>A^{1}[1][2]+A^{1}[2][0]=9$,更新$A^{1}[1][0]=9$, 更新后的方阵标记为$A^{2}$。此时$A^{2}$中保存的就是任意顶点对的最短路径长度

image.png

时间复杂度为$O(\mid V\mid ^3)$

Floyd 算法允许图中有带负权值的边,但不允许有包含带负权值的边组成的回路

也可以用单源最短路径算法来解决每对顶点之间的最短路径问题

对比

image.png

有向无环图描述表达式

若一个有向图中不存在环,则称为有向无环图,简称DAG 图

例如表达式

$$((a+b)*(b*(c+d)) +(c+d)*e)* ((c+d)*e)$$

image.png

观察该表达式,可发现有一些相同的子表达式(c+d)和(c+d)*e，,而在二叉树中,它们也重复出现。若利用有向无环图,则可实现对相同子式的共享,从而节省存储空间

拓扑排序

• 若用DAG 图（有向无环图）表示一个工程,其顶点表示活动,用有向边$<V_{i},V_{j}>$表示活动$V_{i}$必须先于活动$V_{j}$进行的这样一种关系,则将这种有向图称为顶点表示活动的网络,记为 AOV 网
• 在AOV 网中,活动$V_{i}$是活动$V_{j}$的直接前驱,活动$V_{j}$是活动$V_{i}$的直接后继,这种前驱和后继关系具有传递性,且任何活动$V_{i}$不能以它自己作为自己的前驱或后继

提示

拓扑排序和逆拓扑排序都可以用深度优先搜索实现

• 逆拓扑排序在深度优先搜索的退栈返回时打印相应的顶点

拓扑排序

在图论中,由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,称为该图的一个拓扑排序:

1. 每个顶点出现且只出现一次
2. 若顶点A 在序列中排在顶点 B的前面,则在图中不存在从顶点B到顶点A的路径

每个AOV 网都有一个或多个拓扑排序序列

常用方法的步骤：

1. 从AOV 网中选择一个没有前驱的顶点并输出。
2. 从网中删除该顶点和所有以它为起点的有向边。
3. 重复1和2直到当前的 AOV 网为空或当前网中不存在无前驱的顶,点为止。后一种情況说明有向图中必然存在环。

image.png

由于输出每个顶点的同时还要删除以它为起点的边,故采用邻接表存储时拓扑排序的时间复杂度为 $O(\mid V\mid +\mid E\mid)$,采用邻接矩阵存储时拓扑排序的时间复杂度为$O(\mid V\mid^2)$

代码实现

image.png

逆拓扑排序

对一个 AOV 网,如果采用下列步骤进行排序,则称之为逆拓扑排序:

1. 从AOV 网中选择一个没有后继(出度为0)的顶点并输出。
2. 从网中删除该顶点和所有以它为终点的有向边。
3. 重复1和2直到当前的 AOV 网为空。

关键路径

AOE网

在带权有向图中,以顶点表示事件,以有向边表示活动,以边上的权值表示完成该活动的开销(如完成活动所需的时间),称之为用边表示活动的网络,简称 AOE 网

提示

AOE 网中的边有权值;而AOV 网中的边无权值,仅表示顶点之间的前后关系

AOE 网具有以下两个性质:

1. 只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始;
2. 只有在进入某顶,点的各有向边所代表的活动都已结束时,该顶点所代表的事件才能发生。

在AOE 网中仅有一个入度为0的顶点,称为开始顶点(源点),它表示整个工程的开始;网中也仅存在一个出度为0的顶点,称为结束项点(汇点),它表示整个工程的结束。

完成不同路径上的活动所需的时间虽然不同,但是只有所有路径上的活动都己完成,整个工程才能算结束

从源点到汇点的所有路径中,具有最大路径长度的路径称为关键路径,而把关键路径上的活动称为关键活动。

只要找到了关键活动,就找到了关键路径,也就可以得出最短完成时间。

在 AOE 网中，活动的时间余量=结束顶点的最迟开始时间-开始顶点的最早开始时间-该活动的持续时间。

求解关键路径

相关信息

image.png

1. 事件$v_{k}$的最早发生时间$ve(k)$

指从源点$v_{1}$到顶点$v_{k}$以的最长路径长度,计算$ve()$值时,按从前往后的顺序进行,可以在拓扑排序的基础上计算

2. 事件$v_{k}$的最迟发生时间$vl(k)$

$$\begin{aligned}&v l(\text{汇点})=ve(\text{汇点})\\&v l(k)=\operatorname{Min}\left\{vl(j)-\operatorname{Weight}(v_k,v_j)\right\},v_k\text{为 }v_j\text{的任意前驱}\end{aligned}$$

在计算以$vl()$时,按从后往前的顺序进行,可以在逆拓扑排序的基础上计算。

3. 活动$a_{i}$的最早开始时间$e(i)$

若边$<v_{k},v_{j}>$表示活动$a_{i}$,则有$e(i)=ve(k)$

4. 活动$a_{i}$的最迟开始时间$l(i)$

若边$<v_{k},v_{j}>$表示活动$a_{i}$,则有$l(i)=v l(j)-\mathrm{Weight}(v_k,v_j)$

5. $d(i)=l(i)-e(i)$

它是指该活动完成的时间余量,即在不增加完成整个工程所需总时间的情况下,活动$a_{i}$可以拖延的时间。若一个活动的时问余量为零,则说明该活动必须要如期完成,否则就会拖延整个工程的进度,所以称$l(i)-e(i)=0$的活动$a_{i}$是关键活动。

1. 关键路径上的所有活动都是关键活动,它是决定整个工程的关键因素,因此可以通过加快关键活动来缩短整个工程的工期。
2. 网中的关键路径并不唯一,且对于有几条关键路径的网,只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期,只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。