1.4 图的相关应用

图可用于解决现实生活中的许多问题。前面三节介绍了图最基本的概念、图的表示方式以及图的遍历，在此基础之上，本节将以几个实际问题为背景，介绍几种与图相关的经典算法。本节主要内容包括 最小生成树、AOV网与拓扑排序、AOE网与关键路径、最短路径。

1.4.1 最小生成树

现实生活中，人们经常会遇到需要用最小生成树来解决的问题。比如，若要在 n 个城市之间建立通信网，并且建立通信网有其对应的经济成本，如何保证在成本降到最低的前提下建立这个通信网？

我们可以用一个连通网来表示 n 个城市之间的连接关系，顶点表示城市，边表示城市间的通信线路。根据1.1节中介绍的生成树的概念，可以得知，连通这 n 个顶点只需要 n -1条边。对于一个连通网 G ，当采用不同的遍历方式时，会得到不同的生成树，当采用相同的遍历方式但以不同的顶点作为起始点时，也会得到不同的生成树。在所有生成树中权值之和最小的生成树称为 最小生成树 （Minimum cost Spanning Tree，MST）。

至此，我们所研究的问题就转换成了求最小生成树的问题，Prim算法和Kruskal算法是构建最小生成树的两个算法。它们都利用了最小生成树的下列性质：设 G =（ V ， E ）是一个连通网， U 是顶点集 V 的一个非空子集，若（ u ， v ）是一条具有最小权值的边，其中 ， ，则必定存在一棵包含边（ u ， v ）的最小生成树。下面分别介绍这两种算法。

1.Prim算法

假设 G =（ V ， E ）是连通网，其最小生成树 T =（ U ，TE），TE是 G 上最小生成树中边的集合。 T 的初始状态为 ，重复执行以下操作：在所有 ， 的边 中找一条最小权值的边（ u ₀ ， v ₀ ）并入集合TE，同时将 v ₀ 并入 U ，直至 U = V 为止。此时TE中必有 n -1条边，则 T =（ U ，TE）为 G 的最小生成树。Prim算法构造最小生成树的过程如图1-21所示。

2.Kruskal算法

Kruskal算法是一种按权值递增次序选择合适的边来构造最小生成树的方法。假设 G =（ V ， E ）是一个连通图，其最小生成树的初始状态为只有 n 个顶点而无边的非连通图 T =（ V ，{}），每一个顶点自成一个连通分量。然后执行以下操作：按照边的权值由小到大排序，不断选取当前权值最小的边，若该边依附的顶点属于 T 中两个不同的连通分量，则将此边加入 T 中，否则舍弃此边而选择下一条权值最小的边。以此类推，直到 T 中所有顶点都在同一个连通分量上。Kruskal算法构造最小生成树的过程如图1-22所示。

1.4.2 AOV网与拓扑排序

一个无环的有向图称为 有向无环图 （Directed Acyclic Graph，DAG）。DAG图是描述一项工程或系统进行过程的有效工具。几乎所有的工程（Project）都可以分为若干个称作活动（Activity）的子工程，这些子工程之间通常有一定条件的约束，例如某些子工程必须在另一些子工程完成之后才能开始。对于整个工程或系统，该如何判断工程能否顺利进行？接下来介绍的AOV网与拓扑排序将解决这一问题。

1.AOV网

若在一个有向图中，用顶点表示活动，用弧表示活动间的优先关系，则将该有向图称为 顶点表示活动 （Activity On Vertex，AOV）的网络。

AOV网是一种可以形象反映整个工程中各个活动之间的前后关系的有向图。例如，将计算机专业的学生开展的一系列课程看成一个工程，每一门课程都看成是工程中的一项活动，有些课程是基础课，它独立于其他课程，而有些课程必须在其先修课程学完之后才能开始。假设某计算机课程开设的先后关系如表1-1所示。

这种先后关系可以用AOV网清晰地描绘出来，如图1-23所示。

2.拓扑排序

在AOV网中不应该存在环，因为AOV网中的弧代表着活动的先后次序，环的出现就意味着有某项活动是以自己为先决条件的，这在实际活动中是不可能的。因此，对于给定的AOV网应该首先判断网中是否存在环。判断的方法就是对AOV网进行拓扑排序。拓扑排序的定义如下所述。

拓扑排序 （Topological Order）是AOV网中各顶点的线性序列，它使得若存在一条从顶点 v _i 到顶点 v _j 的路径，则在序列中顶点 v _j 出现在顶点 v _i 的后面。拓扑排序的步骤可描述如下：

①从AOV网中选择一个没有前驱的顶点且输出它。

②从网中删除该顶点和所有以它为尾的弧。

③重复①和②，直到AOV网中的顶点全被输出或当前网中不存在无前驱的节点为止。后一种情况则说明AOV网中存在环。

如图1-23所示的AOV网的一个拓扑序列为： C ₁ ， C ₈ ， C ₉ ， C ₂ ， C ₅ ， C ₃ ， C ₄ ， C ₇ ， C ₆ 。

1.4.3 AOE网与关键路径

前面讨论的AOV网可以判断一项工程能否顺利进行，下面将要介绍的AOE网和关键路径可以预计完成整个工程所必需的最短时间。

1.AOE网

AOE（Activity On Edge）网是一个带权无环有向图，其中顶点表示事件（Event），弧表示活动，权值表示完成活动所需的时间。

在AOE网中，只有在某顶点所代表的事件发生后，从该顶点出发的各个有向边所代表的活动才能开始。只有在进入某个顶点的所有有向边所代表的活动都已经结束后，该顶点所代表的事件才能发生。例如，在如图1-24所示的AOE网中， a _k 的值代表完成活动 a _k 所需的时间，该AOE网代表一项包括7项活动和6个事件的工程。事件 v ₀ 代表工程的开始，事件 v ₅ 代表工程的结束，事件 v ₃ 代表着活动 a ₂ 和 a ₃ 已经完成，活动 a ₅ 可以开始。

2.关键路径

由于整个工程只有一个开始点和一个完成点，所以在正常情况（无环）下，AOE网中只有一个入度为0的顶点（称为源点）和一个出度为0的顶点（称为汇点）。从源点到汇点可能有多条路径，其中长度最长的路径称为 关键路径 （Critical Path），把关键路径上的活动称为 关键活动 （Critical Activity）。

对于一个AOE网，计算出每一个顶点的最早完成时间TE（ v _i ）和最迟完成时间TL（ v _i ）。设 μ （ v ）是从出发点 v ₀ （顶点 v _i ）到顶点 v _i （终点 v _n ）的任意一条路径， t （ μ ）（ t （ v ））表示通过 μ （ v ）路径所需的总时间，则TE（ v _i ）和TL（ v _i ）分别满足：

由此可以求得从源点到汇点的关键路径，关键路径上的顶点 v _i 都满足TE（ v _i ）=TL（ v _i ），而其余顶点都有一个缓冲时间（TE与TL之差）。因此，为了缩短整个工程的最早完成时间，只需要缩短关键活动的工期即可。对图1-24中AOE网的各个顶点求解TE与TL值，结果如图1-25所示。从图1-25中可以得出该AOE网的最短路径为< v ₀ ， v ₂ ， v ₄ ， v ₅ >。

1.4.4 最短路径

在一个带权有向图中，把从一个顶点 v ₀ 到图中任意一个顶点 v _i 的一条路径所经过边上的权值之和，定义为该路径的 带权路径长度 （Weighted Path Length），把带权路径长度之和最小的那条路径称为 最短路径 （Shortest Path）。

最短路径问题是图的一个典型应用问题。在日常生活中，人们经常会应用最短路径解决两点之间距离最近的问题。比如，用带权有向图表示一个交通网络，顶点表示城市，边表示城市间的线路，权表示该线路的长度或者经过该线路所花费的时间和费用等。

求最短路径问题常用的算法有 Dijkstra算法 和 Floyd算法 ，下面分别介绍这两种算法。

1.Dijkstra算法

Dijkstra算法通常用来求 单源最短路径问题 （Single-Source Shortest-Path Problem），即求图中某一顶点到其他各顶点的最短路径。Dijkstra提出了一种按照路径长度递增的次序产生最短路径的算法。在该算法中，引入了一个辅助数组dist，它的每个分量dist［ i ］表示当前所找到的从源点 v ₀ 到终点 v _i 的最短路径长度。一般情况下，设置一个集合 S 记录已求得最短路径顶点的集合。假设用一个带权的邻接矩阵arcs表示带权有向图，arcs［ i ］［ j ］表示弧< v _i ， v _j >上的权值。具体算法描述如下：

①初始化工作。集合 S 的初始状态为{0}，若从 v ₀ 到 v _i 有弧，则初值dist［ i ］=arcs［0］［ i ］，否则dist［ i ］=∞。

②从集合 V-S 中求一条长度最短的路径。满足式（1-5）的路径就是从始点 v ₀ 出发的一条最短路径，此路径为（ v ₀ ， v _j ），令 S = S ∪{ j }。

③更新dist数组。对于集合 V-S 中的任一顶点 v _k ，如果dist［ j ］+arcs［ j ］［ k ］<dist［ k ］，则按式（1-6）更新dist［ k ］。

④重复操作。重复②—③操作 n -1次，直到所有的顶点都包含在集合 S 中。

对图1-26a用Dijkstra算法求从顶点 v ₀ 到其余各顶点的最短路径，过程如图1-26b所示。

2.Floyd算法

通过前面介绍的Dijkstra算法，我们可以很容易地求得单源点的最短路径，利用此算法也可以求每一对顶点之间的最短路径，只需要每次选择一个顶点作为源点，重复执行Dijkstra算法 n 次，就可以求得每一对顶点之间的最短路径。

下面介绍如何通过Floyd算法求每一对顶点之间的最短路径，算法基本思想描述如下：

①初始化工作。定义一个 n 阶方阵序列 D ^（-1） ， D ^（0） ，…， D ^{n -1} ，其中 D ^k ［ i ］［ j ］表示从 v _i 到 v _j 的中间顶点的序号不大于 k 的最短路径的长度。初始时，对于任意两个顶点 v _i 和 v _j ， D ^（-1） ［ i ］［ j ］满足

②迭代。逐步试探，在原路径中加入顶点 v _k 作为中间节点（ k =0，1，…， n -1），若增加中间节点后，得到的新路径长度比原来的少，则用新路径代替原来的路径。 D ^{（ k ）} ［ i ］［ j ］满足

经过 n 次迭代后，所得到的 D ^{（ k -1）} ［ i ］［ j ］就是顶点 v _i 到顶点 v _j 的最短路径，方阵 D ^{（ k -1）} 即是图中任意一对顶点之间的最短路径长度。

对图1-27a用Floyd算法求从顶点 v ₀ 到其余各顶点的最短路径，过程如图1-27b所示。