第7章 图结构
Min min; MGraph G; GKind gk=DN; cout<<\建立一个有向网的邻接矩阵G:\\n\ CreateGraph_MG(G,gk); cout<<\有向网G的邻接矩阵为:\\n\ DisplyMG(G); Floyd(min,G); cout<<\弗洛伊德算法的结果为:\\n\ DisplyMin(min); }
运行演示结果为：
建立一个有向网的邻接矩阵G:
输入顶点数vexnum和弧数arcnum:7 12↙ 按某种顺序输入7个顶点的值: 1 2 3 4 5 6 7↙ 输入图中12条边(弧)和权的信息u v w:
1 2 2 1 4 1 2 4 3 2 5 10 3 1 4 3 6 5 4 3 2 4 5 2 4 6 8 4 7 4 5 7 6 7 6 1↙ 有向网G的邻接矩阵为: 0 2 0 1 0 0 0 0 0 0 3 10 0 0 4 0 0 0 0 5 0 0 0 2 0 2 8 4 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 1 0
弗洛伊德算法的结果为: 最短距离矩阵dist为:
<0,0>=0 <0,1>=2 <0,2>=3 <0,3>=1 <0,4>=3 <0,5>=6 <0,6>=5 <1,0>=9 <1,1>=0 <1,2>=5 <1,3>=3 <1,4>=5 <1,5>=8 <1,6>=7 <2,0>=4 <2,1>=6 <2,2>=0 <2,3>=5 <2,4>=7 <2,5>=5 <2,6>=9 <3,0>=6 <3,1>=8 <3,2>=2 <3,3>=0 <3,4>=2 <3,5>=5 <3,6>=4 <4,0>=0 <4,1>=0 <4,2>=0 <4,3>=0 <4,4>=0 <4,5>=7 <4,6>=6 <5,0>=0 <5,1>=0 <5,2>=0 <5,3>=0 <5,4>=0 <5,5>=0 <5,6>=0 <6,0>=0 <6,1>=0 <6,2>=0 <6,3>=0 <6,4>=0 <6,5>=1 <6,6>=0 最短路径上的结点为: <0,1>=0 1 <2,3>=2 0 3 <4,5>=4 6 5 <0,2>=0 3 2 <2,4>=2 0 3 4 <4,6>=4 6 <0,3>=0 3 <2,5>=2 5 <5,0>=no path! <0,4>=0 3 4 <2,6>=2 0 3 6 <5,1>=no path! <0,5>=0 3 6 5 <3,0>=3 2 0 <5,2>=no path! <0,6>=0 3 6 <3,1>=3 2 0 1 <5,3>=no path! <1,0>=1 3 2 0 <3,2>=3 2 <5,4>=no path! <1,2>=1 3 2 <3,4>=3 4 <5,6>=no path! <1,3>=1 3 <3,5>=3 6 5 <6,0>=no path! <1,4>=1 3 4 <3,6>=3 6 <6,1>=no path! <1,5>=1 3 6 5 <4,0>=no path! <6,2>=no path! <1,6>=1 3 6 <4,1>=no path! <6,3>=no path! <2,0>=2 0 <4,2>=no path! <6,4>=no path! <2,1>=2 0 1 <4,3>=no path! <6,5>=6 5
程序运行中所建立的是图7.26(a)所示的有向网G的邻接矩阵，其输出结果是G中任意两点之间的最短路径长度和最短路径上各个顶点的下标序列。该算法的时间复杂度为O(n3)。
-.211.-
第7章 图结构 7.6拓扑排序
拓扑排序是有向图的重要应用之一，它在实际中的应用很广。有向无环图是描述工程和系统进程的有效工具。例如，要完成一项大工程(project)可以把它分为若干个称为活动(activity)的子工程，当这些活动都完成时，整个工程即告结束。而这些活动的安排有时要有特殊的要求，比如有些活动必须安排在另外一些活动已完成以后才能开始，而有些活动并不依赖于任何活动的完成等。类似这样的问题，可以用有向无环图来解决。
7.6.1 AOV网
在有向图中，以顶点表示活动，有向边表示活动之间的优先关系，我们把这样的有向图称为顶点表示活动的网络(Activity On Vertex Network)，简称为AOV网。在AOV网中，若从顶点vi到顶点vj有一条有向路径，则称vi是vj的前驱，vj是vi的后继；若
在AOV网中不允许出现回路，因为如果有回路存在则表示必有某个活动是以自己为先决条件的，即存在活动vi，vi既是其本身的前驱又是其本身的后继，这显然是矛盾的。
例如，图7.30(a)列出了某大学计算机专业学生所学的一些课程，图7.30(b)用有向图表示课程之间的先后关系。
课程号 C1 C2 C3 C4 C5 C6 课程名称 C语言程序设计 离散数学 数据结构 汇编语言 语言设计与分析 计算机组成原理 先导课 无 C1 C1,C2 C1 C3,C4 C11 课程号 C7 C8 C9 C10 C11 C12 课程名称 编译原理 操作系统 高等数学 线性代数 普通物理 数值分析 先导课 C3,C5 C3,C6 无 C9 C9 C1,C9,C10 (a) 某大学计算机专业学生所学的一些课程
由图可以看出，先学习课程C1、C2以后才可以开始学习课程C3，即C1、C2为C3的直接前导课程；只有学习C3、C4以后才可以开始学习课程C5；只有学习C3、C5以后才可以学习
-.212.-
第7章 图结构
课程C7。所以C7的直接前导课程为C3、C5，而C7的所有前导课程为C1、C2、C3、C4、C5。
检测AOV网中是否存在环路的办法是对有向图构造其顶点的拓扑有序序列，若网中所有顶点均在该序列中，则该AOV网中必定不存在环路，否则必有环路存在。
7.6.2拓扑排序
如何安排AOV网中各个活动的先后次序就是拓扑排序问题。所谓拓扑排序，即是把AOV网中各个顶点按照它们之间的优先关系排列成一个线性序列，这个序列称为拓扑有序序列。在AOV网中，如果从顶点vi到顶点vj有有向路径存在，则在拓扑有序序列中，vi必定排在vj的前面。如果在AOV网中存在环路，则不存在该网的拓扑有序序列；否则，任何有向无环网其所有顶点都可以排列在一个拓扑有序序列中。
显然，一个AOV网的拓扑有序序列不是唯一的。对图7.30(b)所示的有向图进行拓扑排序，可以得到多种不同的拓扑有序序列，下面给出其中的三种拓扑有序序列：
?C9,C10,C11,C6,C1,C12,C4,C2,C3,C5,C8,C7??C1,C9,C4,C10,C11,C2,C12,C3,C6,C5,C7,C8? ?C1,C2,C3,C4,C5,C7,C9,C10,C11,C6,C12,C8?对AOV网进行拓扑排序的步骤是：
首先任意选取一个入度为零的顶点输出，再从图中删除该顶点和所有以它为尾的弧。重复以上步骤，直至有向图中全部顶点都被输出，或者还没有输出全部顶点，但已找不到入度为零的顶点为止。第一种情况表明该有向图中不存在有向环路，拓扑排序已完成；对于第二种情况则说明该有向图中存在有向环路。
1．拓扑排序的算法思想
为了实现拓扑排序的方法，可以采用邻接表作为有向图的存储结构，并且在头结点中增加一个存放顶点入度的域(indegree)。每个顶点入度域的值随邻接表动态生成过程中累计得到。也可以另设一个数组(indegree)用于存放所有顶点的入度。在入度数组(indegree)中，入度为0的顶点即为可以删除的没有前驱的顶点。删除顶点以及以该顶点为尾的所有弧的操作，可以通过对弧头顶点入度域的值减1来实现。为了避免重复检测入度为0的顶点，可以另设一个栈(Stack)来存储所有入度为0的顶点下标。下面列出拓扑排序算法的具体步骤：
(1) 如果入度数组(indegree)是另设的，则初始化该数组；
(2) 将邻接表中所有入度为0的顶点下标进栈S，初始化输出顶点计数器count； (3) 在栈S不为空时：
a) 出栈并输出顶点i，count++；
b) 将顶点i的所有直接后继顶点k的入度减1。如果减1后，顶点k的入度为0，则顶点k进栈S。
(4) 如果S为空时count 例如，对图7.30(b)所示的有向图G进行拓扑排序。假定G的邻接表表示如图7.31所示，那么在拓扑排序过程中，各个顶点的入度的变化情况如图7.32所示，零入度顶点栈的变化情况如图7.33所示。由此得到的拓扑排序序列为：C9,C10,C11,C6,C1,C2,C3,C8,C4,C5,C7,C12。 -.213.- 第7章 图结构 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 1 2 1 2 2 0 1 1 3 0 1 2 1 2 1 2 2 0 0 2 C10 0 1 2 1 2 1 2 2 0 1 C11 0 1 2 1 2 0 2 2 1 C6 0 1 2 1 2 2 1 1 C1 0 1 0 2 2 1 0 C2 0 0 2 2 1 0 C3 0 1 1 0 0 C8 0 1 1 0 C4 0 1 0 0 0 0 data C9 C5 C7 C12 图7.32 对图7.31进行拓扑排序过程中各顶点入度的变化情况 0 9 0 0 1 3 2 3 7 3 3 4 6 8 10 10 5 0 0 11 11 11 11 11 11 11 图7.33 零入度栈中顶点的变化情况 2．算法实现 (1) 入度数组和零入度顶点栈的初始化操作 函数void Init_IndegreeStack(int* &indegree,Stack& S,ALGraph G)的功能是，由有向图G的邻接表初始化入度数组indegree[]以及存储零入度顶点下标的栈S。 struct Stack{int t,*s;}; void Init_IndegreeStack(int* &indegree,Stack& S,ALGraph G) { int i,num=G.vexnum; ArcNode* p; indegree=new int[num]; -.214.-