《第7章 图结构》习题解答

第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是vj的直接前驱,vj是vi的直接后继。如果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.-

联系客服:779662525#qq.com(#替换为@)