图的应用

最小生成树

生成树回顾

• 生成树：所有顶点均由边连接在一起，但不存在回路的 图
• 一个图可以有多个不同的生成树
• 所有的生成树具有以下的共同特点:
  • 生成树的顶点个数与图的顶点个数相同
  • 生成图是图的极小连通子图，去掉一条边则非连通
  • $n$ 个结点的连通图的生成树有 $n-1$ 条边
  • 生成树再加一条边会形成回路
• 无向图的生成树:
  • 深度优先生成树
  • 广度优先生成树

最小生成树

对于一个无向网, 该网所得有生成树中, 各边权值和最小的生成树叫做最小生成树.

典型用途: 用最小的成本在城市之间建立通信网

MST 性质:

在生成树的构造过程中, 图的 $n$ 个顶点分为两个集合:

• 已经位于生成树的顶点集: U
• 尚未落入生成树的顶点集: V-U

接下来应该加入连通U与V-U中顶点的边中选取权值最小的边, 且不能形成环路

Prim 算法

思想:

• 开始时 U 中仅包含一个顶点, 在 U 集合中找一个顶点, V-U 中找一个顶点, 将依附于这两个顶点的边加入生成树, 这条边具有的特点是: 符合要求的边中权值最小.

Kruskal 算法

思想:

• 贪心. 一开始最小生成树的状态为 n 个顶点而无边的非连通图 T=(V,{}), 每个顶点自成一个连通分量.
• 在边集合 E 中选取权值最小的边, 若该边依附的顶点落在 T 的不同连通分量上(即加入这条边不会形成环) , 则将这条边加入T ,否则舍去这条边, 选取下一条代价最小的边.

两个算法的比较:

算法	Prim	kruskal
思想	选择点	选择边
复杂度	$O(n^2)$	$O(e\log_2e)$
适用范围	稠密图	稀疏图

最短路径

典型应用: 交通网络问题:

• 顶点:地点
• 弧:表示两个地点之间连通
• 弧上的权值: 两个地点之间额距离, 交通费或者途中花费的时间等等

问题抽象: 在有向网中 A 点到 B 点的多条路径中, 寻找一条权值和最小的路径,称为最短路径.

与最小生成树的区别: 最短路径不一定要包括所有的顶点或边.

Dijkstra 算法—单源最短路径

1. 初始化:先找出源点 $V_0$ 到各终点 $V_K$ 的直达路径$(V_0,V_K)$ ,即通过一条弧到达的路径. 若不存在, 权值记为无穷大.$S = {V_0},T = V-S$

2. 选择:从这些路径中找一条最短的路径$(V_0,U)$, $U$ 加入 $S$

3. 更新:然后对其余各条路径进行适当调整:

   若图中存在路径 $(U,V_K)$ 使得 $(V_0,U)+(U,V_K)<(V_0,V_K)$ ,

   则用路径 $(V_0,U)+(U,V_K)$ 代替 $(V_0,V_K)$

   再调整后的各条路径中,再在 $T$ 寻找长度最短的路径, 以此类推

Floyd 算法—所有顶点间的最短路径

求所有顶点间的最短路径：

• 以每一个顶点为源点，重复执行 Dijkstra 算法 n 次 $O(n^3)$
• Floyd 算法

初始：建立一个邻接矩阵, 对角线元素置为0, 不直接相连的顶点置为$\infty$ , 否则置为权值. 然后依次在原来的直接路径中加入中间顶点, 若加入后路径变短, 则修改. 所有顶点探查完毕后, 结束.

过程图

$$\text { 初始 : }\left[\begin{array}{lll} 0 & 4 & 11 \\ 6 & 0 & 2 \\ 3 & \infty & 0 \end{array}\right] \text { 路径: }\begin{array}{|l|l|r|} \hline & \mathrm{AB} & \mathrm{AC} \\ \hline \mathrm{BA} & & \mathrm{BC} \\ \hline \mathrm{CA} & & \\ \hline \end{array}$$ $$\begin{array}{l} \text { 加入A : }\left[\begin{array}{lll} 0 & 4 & 11 \\ 6 & 0 & 2 \\ 3 & {\color{blue}7} & 0 \end{array}\right]\text { 路径 : } \begin{array}{|l|l|l|} \hline & \mathrm{AB} & \mathrm{AC} \\ \hline \mathrm{BA} & & \mathrm{BC} \\ \hline \mathrm{CA} & \mathrm{\color{blue} {CAB}} & \\ \hline \end{array} \end{array}$$ $$\text { 加入B: }\left[\begin{array}{lll} 0 & 4 & \color{red} 6 \\ 6 & 0 & 2 \\ 3 & {\color{blue}7} & 0 \end{array}\right] \text { 路径: } \begin{array}{|l|l|r|} \hline & \mathrm{AB} & \mathrm{\color{red}ABC} \\ \hline \mathrm{BA} & & \mathrm{BC} \\ \hline \mathrm{CA} & \mathrm{\color{blue}CAB} & \\ \hline \end{array}$$ $$加入C :\left[\begin{array}{lll}0 & 4 & \color{red}6 \\{\color{green} 5} & 0 & 2 \\3 & \ {\color{blue}7} & 0\end{array}\right] \text{路径: }\begin{array}{|l|l|r|} \hline & \mathrm{AB} & \mathrm{\color{RED}{ABC} } \\ \hline \mathrm{\color{green} {BCA} } & & \mathrm{BC} \\ \hline \mathrm{CA} &\mathrm{\color{blue} {CAB} } & \\ \hline \end{array}$$

用顶点表示活动的网络(AOV网络)

把一个工程分为若干个子工程, 只要这些子子工程(活动)完成了, 工程就完成了.

AOV网络: 用一个有向图表示一个工程的各个子工程的相互制约关系, 顶点表示活动, 边表示活动之间的制约

拓扑排序

$$\begin{array}{|l|l|l|}\hline \text { 课程代号 } & {\text { 课程名称 }} & {\text { 先修课 }} \\\hline \mathrm{C} 1 & \text { 程序设计基础 } & \text { 无 } \\\hline \mathrm{C} 2 & \text { 离散数学 } & \mathrm{C} 1 \\\hline \mathrm{C} 3 & \text { 数据结构 } & \mathrm{C} 1, \mathrm{C} 2 \\\hline \mathrm{C} 4 & \text { 汇编语言 } & \mathrm{C} 1 \\\hline \mathrm{C} 5 & \text { 语言的设计和分析 } & \mathrm{C} 3, \mathrm{C} 4 \\\hline \mathrm{C} 6 & \text { 计算机原理 } & \mathrm{C} 11 \\\hline \mathrm{C} 7 & \text { 编译原理 } & \mathrm{C} 3, \mathrm{C} 5 \\\hline \mathrm{C} 8 & \text { 操作系统 } & \mathrm{C} 3, \mathrm{C} 6 \\\hline \mathrm{C} 9 & \text { 高等数学 } & \text { 无 } \\\hline \mathrm{C} 10 & \text { 线性代数 } & \mathrm{Cg} \\\hline \mathrm{C} 11 & \text { 普通物理 } & \mathrm{C} 9 \\\hline \mathrm{C} 12 & \text { 数值分析 } & \mathrm{C} 1, \mathrm{C} 9, \mathrm{C} 10 \\\hline\end{array}$$

由上表得 AOV 图:

AOV 网络特点:

• i 到 j 有一条有向路径, 则 i 为 j 的前驱, j 为 i 的后继.
• 若 为图中有向边, 则 i 为 j 的直接前驱, j 为 i 的直接后继.
• 由于AOV 网络中, 前驱表示先决条件, 因此在 AOV 网络中不允许出现有向环, 对于给定的 AOV 网络, 必须判断它是否存在有向环——拓扑排序

拓扑排序的定义:

• 将 AOV 网络中各个顶点排列成一个线性有序序列, 保证原 AOV 网络中的前驱顶点一定位于后继顶点之前.

步骤:

• 在网络中找一个没有前驱的顶点输出.
• 在网络中删除这个顶点以及所有出边.
• 不断重复, 直到找不到无前驱的顶点(此时网络中仍然存在顶点,则该AOV图中含有向环)或者所有的顶点都已经输出.

如上述 AOV 图可以这样拓扑排序(注意不唯一):

用边表示活动的网络 (AOE 网络)

AOE 网络: 用有向边表示活动, 有向边上的权值表示持续时间,顶点表示事件.

如图所示, 事件表示在它值钱的活动已经完成, 之后的活动可以开始.

对应的有向图:

AOE 网络应用:

• 估计工程总共需要的时间
• 为缩短工程所需时间, 应该加快哪些活动?

关键路径

定义: 路径长度最长的路径

• 入度为零的点: 源点, 表示工程开始
• 出度为零的点: 汇点, 表示工程结束

只要找到了关键路径, 上面的两个问题就能解决.

几个描述量:

• ve(vj):事件 $v_j$ 最早发生时间
• vl(vj):事件 $v_j$ 最晚发生时间
• e(i): 活动 $a_i$ 最早开始时间
• l(i):活动 $a_i$ 最晚开始时间
• l(i)-e(i): 完成活动 $a_i$ 的时间余量, 即在这一段时间内任何时候开始都不会影响到进度.

关键活动: 关键路径上的活动,l(i)- e(i)==0.只要找到关键活动, 就能构建关键路径.

对于一个事件来讲, 它相邻的活动可能不止两个;对于一个活动来讲, 他相邻的事件仅有确定的两个.

$v_i-a(不止一个)->v_j-b->v_k$

需要计算的量:

• $e(b) = ve(v_j)$
• $l(b) = vl(vk)-w{j,k}$
• $ve(vj) = \max(ve(v_i)+w{i,j})$
• $vl(vj)=\min(vl(v_k)-w{j,k})$

步骤:

1. 正向计算 $ve()$

   $ve(v_1)= 0$, 则根据递推公式可以求出

2. 反向计算 $vl()$

   由最后一个事件的最晚结束时间往前推

3. 求各个活动的 $l()-e()$

举个例子：

对于这张网络:

有如下分析:

$$\begin{array}{|c|r|c|} \hline \text { 顶点 } & {\text { ve }} & {\text { vI }} \\ \hline \text { v1 } & 0 & 0 \\ \hline \text { v2 } & 6 & 6 \\ \hline \text { v3 } & 4 & 6 \\ \hline \text { v4 } & 5 & 8 \\ \hline \text { v5 } & 7 & 7 \\ \hline \text { v6 } & 7 & 10 \\ \hline \text { v7 } & 16 & 16 \\ \hline \text { v8 } & 14 & 14 \\ \hline \text { v9 } & 18 & 18 \\ \hline \end{array}\begin{array}{|l|l|l|l|} \hline \text { 活动 } & \mathrm{e} & \mathrm{l} & \mathrm{l}-\mathrm{e} \\ \hline \mathrm{a} 1 & 0 & 0 & 0 \\ \hline \mathrm{a} 2 & 0 & 2 & 2 \\ \hline \mathrm{a} 3 & 0 & 3 & 3 \\ \hline \mathrm{a} 4 & 6 & 6 & 0 \\ \hline \mathrm{a} 5 & 4 & 6 & 2 \\ \hline \mathrm{a} 6 & 5 & 8 & 3 \\ \hline \mathrm{a} 7 & 7 & 7 & 0 \\ \hline \mathrm{a} 8 & 7 & 7 & 0 \\ \hline \mathrm{a} 9 & 7 & 10 & 3 \\ \hline \mathrm{a} 10 & 16 & 16 & 0 \\ \hline \mathrm{a} 11 & 14 & 14 & 0 \\ \hline \end{array}$$

则关键路径为:

     
V1→V2→V5→V8/V7→V9

分析:

• 两个顶点之间存在多条关键路径, 需要同时缩短这些关键路径以减少总的时间.
• 若关键事件缩减过多, 会造成它不再是关键事件.