数据结构—图的应用

6.4图的应用

概念回顾—生成树

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

• 一个图可以有许多棵不同的生成树、
• 含有n个顶点 n-1 条边的图不一定是生成树
• 所有生成树具有以下共同特点
  • 生成树的顶点个数与图的顶点个数相同；
  • 生成树是图的极小连通子图，去掉一条边则非连通；
  • 一个有n个顶点的连通图的生成树有 n-1 条边；
  • 在生成树中再加一条边必然形成回路。
  • 生成树中任意两个顶点间的路径是唯一的；

6.4.1无向图的生成树

​ 设图G=(V,E)是个连通图，当从图任一顶点出发遍历图G时，将边集E(G)分层两个集合T(G)和B(G)。其中T(G)是遍历图时所经过的边的集合，B(G)是遍历图时未经过的边的集合。显然，G1(V,T)是图G的极小连通子图。即子图G1是连通图G的生成树。

6.4.2最小生成树

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

1、构造最小生成树

构造最小生成树的算法很多，其中多数算法都利用了MST的性质。

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

MST性质解释：

​ 在生成树的构造过程中，图中n个顶点分属两个集合：

• 已落在生成树上的顶点集：U

• 尚未落在生成树上的顶点集：V-U

  接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。

2、构造最小生成树算法

普里姆（Prim）算法

算法思想：

• 设N=（V,E）是连通网，TE是N上最小生成树中边的集合。
• 初始令U={u0}，（u0∈V），TE={}。
• 在所有u∈U，v∈V-U的边（u，v）∈E中，找一条代价最小的边（u0，v0）。
• 将（u0,v0）并入集合TE，同时v0并入U。
• 重复上述操作直至U=V为止，则T=（V,TE）为N的最小生成树。

克鲁斯卡尔（Kruskal）算法

算法思想：

• 设连通图N=（V,E），令最小生成树初始状态只有n个顶点而无边的非连通图T=(V,{})，每个顶点自成一个连通分量。
• 在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上（即：不能形成环），则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边。
• 依此类推，直至T中所有顶点都在同一连通分量上为止。

最小生成树可能不唯一

两种算法比较

算法名	普里姆算法	克鲁斯卡尔算法
算法思想	选择点	选择边
时间复杂度	O(n2) (n为顶点数)	O(eloge) (e为边数)
适应范围	稠密图	稀疏图

6.4.3最短路径

典型用途：交通网络的问题—从甲地到乙地之间是否有公路连通？在有多条通路的情况下，哪一条路最短？

交通网络用有向网来表示：

顶点——表示地点

弧——表示两个地点有路连通，

弧上的权值——表示两地点之间的距离，交通费或途中所花费的时间等。

​ 如何能够使一个地点到另一个地点的运输时间最短或运费最省？这就是一个求两个地点间的最短路径问题。

问题抽象：在有向网中A点（源点）到达B点（终点）的多条路径中个，寻找一条各边权值之和最小的路径，即最短路径。

​ 最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n-1条边。

第一类问题：两点间最短路径

第二类问题：某源点到其他各点最短路径

两种常见的最短路径问题：

1. 单源最短路径—用**Dijkstra（迪杰斯特拉）**算法
2. 所有顶点间的最短路径—用**Floyd（弗洛伊德）**算法

1、Dijkstra算法

• 初始化：先找出从源点v0到各终点vk的直达路径（v0，vk），即通过一条弧到达的路径。

• 选择：从这些路径中找出一条长度最短的路径（v0，u）

• 更新：然后对其余各条路径进行适当的调整：

  • 若在图中存在弧（u，vk），且（v0，u）+（u，vk）<（v0，vk），则以路径（v0，u，vk）代替（v0，vk）。

• 在调整后的各条路径中，再找长度最短的路径，依此类推。

迪杰斯特拉（Dijkstra）算法：按路径长度递增次序产生最短路径。

1. 把V分成两组：

   • S：已求出最短路径的顶点的集合。
   • T=V-S：尚未确定最短路径的顶点集合。

2. 将T中顶点按最短路径递增的次序加入到S中。

   保证（1）从源点v0到S中各顶点的最短路径长度都不大于从v0到T中任何顶点的最短路径长度。

   ​ （2）每个顶点对应一个距离值：

   ​ S中顶点：从v0到此顶点的最短路径长度。

   ​ T中顶点：从v0到此顶点的只包括S中顶点作中间顶点的最短路径长度。

所有顶点间的最短路径：

方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次。

方法二：弗洛伊德（Floyd）算法。

2、Floyd算法

算法思想：

• 逐个顶点试探
• 从vi到vj的所有可能存在的路径中
• 选出一条长度最短的路径

例如：采用Floyd算法，求图中各顶点之间最短路径

求最短路径步骤：

​ 初始时设置一个n阶方阵，令其对角线元素为0，若存在弧<vi,vj>，则对应元素为权值，否则为∞

​ 逐步试着在原直接路径中增加中间顶点，若加入中间顶点后路径变短，则修改之；否则，维持原值。所有顶点试探完毕，算法结束。

6.4.4拓扑排序

1、有向无环图

有向无环图：无环的有向图，简称DAG图（Directed Acycline Graph）

​ 有向无环图常用来描述一个工程或系统的进行过程。（通常把计划、施工、生产、程序流程等当成是一个工程）

​ 一个工程可以分为若干个子工程，只要完成了这些子工程（活动），就可以导致整个工程的完成。

**AOV网：**拓扑排序

​ 用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV网（Activity Vertex network）。

​ 特点：

• 若从 i 到 j 有一条有向路径，则 i 是 j 的前驱；j 是 i 的后继。
• 若<i,j>是网中有向边，则 i 是 j 的直接前驱；j 是 i 的直接后继。
• AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谬的。

问题：如何判别AOV网中是否存在回路？

**AOE网：**关键路径

​ 用一个有向图表示一个工程的各子工程及其相互制约的关系，以弧表示活动，以顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网，简称为AOE网（Activity On Edge）。

拓扑排序

​ 在AOV网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若AOV网中有弧<i,j>存在，则在这个序列中，i 一定排在 j 的前面，具有这个性质的线性序列称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序。

拓扑排序的方法：

• 在有向图中选一个没有前驱的顶点且输出之。
• 从图中删除该顶点和所有以它为尾的弧。
• 重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。

一个AOV网的拓扑序列不是唯一的

检测AOV网中是否存在环方法：

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

关键路径

​ 把工程计划表示为边表示活动的网络，即AOE网，用顶点表示事件，弧表示活动，弧的权表示活动持续时间。

事件表示在它之前的活动已经完成，在它之后的活动可以开始。

对于AOE网，我们关心两个问题：

1. 完成整项工程至少需要多少时间？
2. 那些活动是影响工程进度的关键？

关键路径——路径长度最长的路径。

路径长度——路径上各活动持续时间之和。

如何确定关键路径，需要定义4个描述量：

ve(vj)——表示事件 vj 的最早发生时间。

​ 例如：ve(v1)=0 ve(v2)=30

vl(vj)——表示事件 vj 的最迟发生时间。

​ 例如：vl(v4)=165

e(i)——表示活动 ai 的最早开始时间。

​ 例如：e(a3)=30

l(i)——表示活动 ai 的最迟开始时间。

​ 例如：l(a3)=120

l(i) - e(i)——表示完成活动 ai 的时间余量。

​ 例如：l(3) - e(3)=90

关键活动——关键路径上的活动，即 l(i)==e(i)（即l(i) - e(i) == 0）的活动。

关键路径的讨论

1. 若网中有几条关键路径，则需加快同时在几条关键路径上的关键活动。

   如：a11,a10,a8,a7。

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

3. 处于所有的关键路径上的活动完成时间不能缩短太多，否则会使原来的关键路径变成不是关键路径。这时，必须重新寻找关键路径。如：a1由6天变成3天，就会改变关键路径。