拓扑和最短路径

7.5.1拓扑排序数学基础：

什么是拓扑排序(TopologicalSort)?简单地说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。回顾离散数学中关于偏序和全序的定义：若集合X上的关系R是自反的、反对称的和传递的，则称只是集合X上的偏序关系。设R是集合X上的偏序(PartialOrder)，如果对每个x,y∈X必有xRy或yRx，则称R是集合X上的全序关系。

直观地看，偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较。例如，图所示的两个有向图，图中弧(x,y)表示x≤y，则(a)表示偏序，(b)表示全序。若在(a)的有向图上人为地加一个表示v2≤v3的弧(符号“≤”表示v2领先于v3)，则(a)表示的亦为全序，且这个全序称为拓扑有序(TopologicalOrder)，而由偏序定义得到拓扑有序的操作便是拓扑排序。

(a)表示偏序(b)表示全序图1表示偏序和全序的有向图v2v3v1v4v4v3v2v1实际问题：

一个表示偏序的有向图可用来表示一个流程图。它或者是一个施工流程图，或者是一个产品生产的流程图，再或是一个数据流图(每个顶点表示一个过程)。图中每一条有向边表示两个子工程之间的次序关系(领先关系)。例如，一个软件专业的学生必须学习一系列基本课程，其中有些课程是基础课，它独立于其它课程，如《高等数学》；而另一些课程必须在学完作为它的基础的先修课程才能开始。如在《程序设计基础》和《离散数学》学完之前就不能开始学习《数据结构》。这些先决条件定义了课程之间的领先(优先)关系。这个关系可以用有向图更清楚地表示。图中顶点表示课程，有向边(弧)表示先决条件。若课程i是课程j的先决条件，则图中有弧<i，j>。建立模型：

用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网(ActivityOnVertexNetwork)，简称AOV-网。在网中，若从顶点i到顶点j有一条有向路径，则i是j的前驱；j是i的后继。若<i，j>是网中一条弧，则i是j的直接前驱；j是i的直接后继。

注意：

在AOV-网中不应该出现有向环，因为存在环意味着某项活动应以自己为先决条件。若设计出这样的流程图，工程便无法进行。而对程序的数据流图来说，则表明存在一个死循环。因此，对给定的AOV-网应首先判定网中是否存在环。检测的办法是对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV-网中必定不存在环。

以图7.28(a)中的有向图为例，图中v1，和v6没有前驱，则可任选一个。假设先输出v6,在删除v6及弧<v6，v4>，<v6，v5>之后，只有顶点v1没有前驱，则输出v1且删去v1及弧<v1，v2>、<v1，v3>和<v1,v4>，之后v3和v4都没有前驱。依次类推，可从中任选一个继续进行。

最后得到该有向图的拓扑有序序列为：

v6-v1-v4-v3-v2-v5

v2v5v5v1v2v3v5v4v6v4v1v5v3v2v4v5v3v2v3v5v2(a)(b)(c)(d)(e)(f)

图7.28AOV-网及其拓扑有序序列产生的过程

如何在计算机中实现?

针对上述两步操作，我们可采用邻接表作有向图的存储结构，且在头结点中增加一个存放顶点入度的数组(indegree)。入度为零的顶点即为没有前驱的顶点，删除顶点及以它为尾的弧的操作，则可换以弧头顶点的入度减1来实现。为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点，由此可得拓扑排序的算法。StatusTopologicalSort(ALGraphG){

//有向图G采用邻接表存储结构。若G无回路，则输出

//G的顶点的1个拓扑序列并返回OK，否则ERROR。

FindInDegree(G，indegree)；

//对各顶点求入度indegree[0..vernum-1]

InitStack(S)；

for(i=0；i<G.vexnum；++i)

if(!indegree[i])Push(S，i)//建零入度顶点栈,s入度为0者进栈

count=0；

//对输出顶点计数

while(!StackEmpty(S)){Pop(S，i)；

printf(i，G.vertices[i].data)；++count；

//输出i号顶点并计数

for(p=G.vertices[i].firstarc；p；p=p->nextarc){k=p->adivex；

//对i号顶点的每个邻接点的入度减1if(！(--indegree[k]))Push(S，k)；//若入度减为0，则入栈

}//for}//whileif(count<G.vexnum)returnERROR；//该有向图有回路

elsereturnOK；}//TopologicalSort

算法7.12

ShortestPathAlgorithms最短路径

问题背景：假若要在计算机上建立一个交通咨询系统则可以采用图的结构来表示实际的交通网络。图中顶点表示城市，边表示城市间的交通联系。这个咨询系统可以回答旅客提出的各种问题。

首先，我们来看一个简单的图的最短路径问题。例如，一位旅客要从A城到B城，他希望选择一条途中中转次数最少的路线。假设图中每一站都需要换车，则这个问题反映到图上就是要找一条从顶点A到B所含边的数目最少的路径。我们只须从顶点A出发对图作广度优先搜索，一旦遇到顶点B就终止。由此所得广度优先生成树上，从根顶点A到顶点B的路径就是中转次数最少的路径，路径上A与B之间的顶点就是途径的中转站数。有时，对于旅客来说，可能更关心的是节省交通费用；而对于司机来说，里程和速度则是他们感兴趣的信息。为了在图上表示有关信息，可对边赋以权，权的值表示两城市间的距离，或途中所需时间，或交通费用等等。此时路径长度的度量就不再是路径上边的数目，而是路径上边的权值之和。考虑到交通图的有向性(如航运，逆水和顺水时的船速就不一样)，本节将讨论带权有向图，并称路径上的第一个顶点为源点(Sourse)，最后一个顶点为终点(Destination)。下面讨论两种最常见的最短路径问题。（所谓最短路径问题是指：如果从图中某一顶点（称为源点）出发到达另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和达到最小。）一、边上权值非负情形的单源最短路径问题问题描述：给定带权有向图G和源点v，求从v到G中其余各顶点的最短路径。限定各边上的权值大于或等于0。具体实例分析：例如，图7.34所示带权有向图G中从v0到其余各顶点之间的最短路径，如图7.35所示。

图7.34图7.35

始点终点最短路径路径长度v0v1v2v3v4v5无(v0,v2)(v0,v4,v3)(v0,v4)(v0,v4,v3,v5)10503060v5v4v3v2v1v0

1006030101020

550迪杰斯特拉算法：

迪杰斯特拉(Dijkstra)提出了一个按路径长度递增的次序，逐步产生最短路径的算法。首先求出长度最短的一条最路径，然后参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。具体做法：

设集合S中存放已经求出的最短路径的终点，初始状态时，集合S中只有一个源点，不妨设为v0。以后每求得一条最短路径(v0,…,vk)，就将vk加到集合S中，直到全部顶点都加入到集合S中，算法就可以结束了。迪杰斯特拉算法示例：

终点从v0到各终点的D值和最短路径的求解过程v1

∞

∞

∞

∞

∞v210,(v0,v2)v3

∞60,(v0,v2,v3)50,(v0,v4,v3)v430,(v0,v4