武汉软件工程职业学院数据结构算法和算法分析.doc

第二讲 算法和算法分析

第一章绪论

1．、理解重点词语。
4．有感情地朗读课文。

Ø 教学重点：
Ø 教学难点：
Ø 授课内容

5.6 有向无环图及其应用
5.6.1 拓扑排序
有向无环图可以用来描述一项工程或任务的进行过程。 在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：
①先后关系，即必须在一子项目完毕后，才干开始实行另一个子项目；
②子项目之间无顺序规定，即两个子项目可以同时进行，互不影响。
 实际问题：
    一个表达偏序的有向图可用来表达一个流程图。它或者是一个施工流程图，或者是一个产品生产的流程图，再或是一个数据流图(每个顶点表达一个过程)。图中每一条有向边表达两个子工程之间的顺序关系(领先关系)。
在工厂中，一件设备的生产涉及许多工序，各工序之间也存在这两种关系。学校里某个专业的课程学习，有些课程是基础课，它们可以独立于其它课程，即无前导课程；有些课程必须在一些课程学完后才干开始学。 这些类似的问题都可以用有向图来表达，我们把这些子项目、工序、课程当作一个个顶点称之为活动(Activity)。
假如从顶点Vi到Vj之间存在有向边< Vi，Vj>,则表达活动i必须先于活动j进行。这种图称做顶点表达活动的网络(Activity On Vertex network,简称AOV网络)。
    例如，一个软件专业的学生必须学习一系列基本课程(如图7.26所示)，其中有些课程是基础课，它独立于其它课程，如《高等数学》；而另一些课程必须在学完作为它的基础的先修课程才干开始。如在《程序设计基础》和《离散数学》学完之前就不能开始学习《数据结构》。这些先决条件定义了课程之间的领先(优先)关系。这个关系可以用有向图更清楚地表达，如图7.27所示。图中顶点表达课程，有向边(弧)表达先决条件。若课程i是课程j的先决条件，则图中有弧 <i，j>。
    建立模型：
    这种用顶点表达活动，用弧表达活动间的优先关系的有向图称为顶点表达活动的网 (Activity On Vertex Network)，简称AOV-网。在网中，若从顶点i到顶点j有一条有向途径，则i是j的前驱；j是i的后继。若<i，j>是网中一条弧，则i是j的直接前驱；j是i的直接后继。
注意：
    在AOV-网中不应当出现有向环，由于存在环意味着某项活动应以自己为先决条件。若设计出这样的流程图，工程便无法进行。而对程序的数据流图来说，则表白存在一个死循环。因此，对给定的AOV-网应一方面鉴定网中是否存在环。检测的办法是对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV-网中必然不存在环。
【例如】表5-6-1是某校计算机专业的课程及其互相之间的关系，它相应的AOV网络如图5-6-1所示。

表5-6-1 某专业课程设立

图5-6-1（a） AOV网络
在AOV网络中，假如顶点Vi的活动必须在顶点Vj的活动以前进行，则称Vi为Vj的前趋顶点，而称Vj为Vi的后继顶点。这种前趋后继关系有传递性。AOV网络中一定不能有有向环路。例如在图5-6-1（b）那样的有向环路中，V2是V3的前趋顶点，V1是V2的前趋顶点，V3又是V1的前趋顶点，环路表达顶点之间的先后关系进入了死循环。
因此，对给定的AOV网络一方面要鉴定网络中是否存在环路，只有有向无环路网络在应用中才有实际意义。
所谓“拓扑排序”就是将AOV网络中的各个顶点(各个活动)排列成一个线性有序序列，使得所有规定的前趋、后继关系都能得到满足。由于AOV网络中有些顶点之间没有顺序规定，它们在拓扑有序序列中的位置可以任意颠倒，所以拓扑排序的结果一般并不是唯一的。通过拓扑排序还可以判断出此AOV网络是否包具有有向环路，若有向图G所有顶点都在拓扑排序序列中，则AOV网络必然不包具有有向环路。
如何进行拓扑排序?
    解决方案：
        解决的方法很简朴：
拓扑排序方法
(1) 在AOV网中选择一个没有前驱（即入度为0）的顶点，并把它输出；
(2) 从网络中删去该顶点和从该顶点发出的所有有向边；
(3) 反复执行上述两步，直到网中所有的顶点都被输出 (此时，原AOV网络中的所有顶点和边就都被删除掉了)。
假如进行到某一步，无法找到无前趋的顶点，则说明此AOV网络中存在有向环路，碰到这种情况，拓扑排序就无法进行了。

（a） （b） （c） （d） （e） （f）
图5-6-2 AOV网及拓扑序列的产生过程
其中：
（a）AOV网；(b)输出v0后；（c）输出v5后；（d）输出v3后；（e）输出v2后；（f）输出v1后。
这样得到的一个拓扑排序序列为：v0, v5, v3, v2, v1, v4
如何在计算机中实现?
为了实现拓扑排序，针对上述两个环节，采用邻接表作为有向图的存储结构，并且在表结点中增设一个入度，存放顶点的入度。例如图5-6-2种的AOV网的邻接表如图5-6-3（a）所示。这样，入度域为零的表结点及时无前驱的顶点，删除该顶点及它为尾的弧的操作，则可以转换为将它的所有弧头顶点的入度减1来实现 。

（a） 图5-6-2（a）的邻接链表

图5-6-3 AOV网的邻接表达
为了避免在每一次选入度为零的顶点时反复扫描表头数组中的入度与作为链栈域，存放下一个入度为零的顶点，-1表达栈底，栈顶指针为top，寄生在表头数组的入度域中的入度为零的顶点栈链的初始状态如图5-6-3（b）所示。此时栈顶指针top=5指出v5的入度为零，v5的入度域为0表达下一个入度为零的顶点是v0，v0的入度为-1表达v0是栈底。这样，拓扑排序算法可以形式地描述如下：
（1）扫描顶点表，将入度为零的顶点入栈；
（2）while （栈非空）
{ 将栈顶vj探出并输出之；
在邻接表中查vj的直接后继vk，把vk
的入度减1，若vk的入度为零则进栈；
}
（3）若输出的顶点数小于n，则表达则有回路；否则拓扑排序正常结束。
算法5.10
/* AOV网的邻接表表达 */
typedef struct arcnode{
int adjvex;
struct arcnode * nextarc;
}
Arcnode;
typedef struct vnode{
Vextype data;
Int indegree; /* 入度域 */
Arcnode * firstarc;
}vnode;

5.5.2 关键途径
    与AOV-网相相应的是AOE-网(Activity On Edge)即边表达活动的网。AOE-网是一个带权的有向无环图，其中，顶点表达事件(Event)，弧表达活动，权表达活动连续的时间。通常，AOE-网可用来估算工程的完毕时间。
    实际问题：
    [例如] 图5-6-4是一个假想的有11项活动的AOE-网。其中有9个事件v1，v2，v3，…，v9，每个事件表达在它之前的活动已经完毕，在它之后的活动可以开始。如v1表达整个工程开始，v9表达整个工程结束，v5表达a4和a5已经完毕，a7和a8可以开始。与每个活动相联系的数是执行该活动所需的时间。比如，活动a1需要6天，a2需要4天等。

图5-6-4 一个AOE-网
•
    和AOV-网不同，对AOE-网有待研究的问题是：
    (1)完毕整项工程至少需要多少时间?
    (2)哪些活动是影响工程进度的关键?
由于在AOE-网中有些活动可以并行地进行，所以完毕工程的最短时间是从开始点到完毕点的最长途径的长度(这里所说的途径长度是指途径上各活动连续时间之和，不是途径上弧的数目)。途径长度最长的途径叫做关键途径(Critical Path)。假设开始点是v1，从v1到vi的最长途径长度叫做事件vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表达的活动的最早开始时间。我们用e(i)表达活动ai的最早开始时间。还可以定义一个活动的最迟开始时间l(i)，这是在不推迟整个工程完毕的前提下，活动ai最迟必须开始进行的时间。两者之差l(i)-e(i)意味着完毕活动ai的时间余量。我们把l(i)=e(i)的活动叫做关键活动。显然，关键途径上的所有活动都是关键活动，因此提前完毕非关键活动并不能加快工程的进度。因此，分析关键途径的目的是辨别哪些是关键活动，以便争取提高关键活动的工效，缩短整个工期。
在描述关键途径的算法时，设活动ai由弧<j,k>表达，要拟定如下几个相关的量：
(1) 事件Vj的最早出现时间和活动的最早开始时间：从源点V1到某顶点Vj的最长途径长度叫作事件j的最早出现时间，表达成ev[j]。顶点Vj的最早出现时间ev[j]决定了从Vj指出的各条边所代表活动的最早开始时间，由于事件j不出现，它后面的各项活动就不能开始。我们以e[i]表达活动ai的最早开始时间。显然e[i]= ev[j] 。
(2) 活动ai的最迟开始时间：在不影响整个工程准时完毕的前提下，此项活动最迟的必须开始时间，表达成L[i]。只要某活动ai有L[i]=e[i]的关系，我们就称ai为关键活动。关键活动只允许在一个拟定的时间开始，再早，它前面的事件还没出现，尚不能开始；再晚，又会延误整个工程的准时完毕。由于完毕整个工程所需的时间是由关键途径上各边权值之和所决定的，显然关键途径上各条边所相应的活动都是关键活动。
(3) 事件j的最迟出现时间：即事件j在不延误整个工程的前提下允许发生的最迟时间，表达为Lv[j]。对某条指向顶点Vj的边所代表的活动ai可得到：
L[i]= Lv[j]-(活动ai所需时间)
也就是活动ai必须先于它后面事件的最迟出现时间开始，提前的时间为进行此活动所需的时间。 图5-6-5所示为活动开始时间与事件出现时间的关系。

图5-6-5 活动开始时间与事件出现时间的关系
拟定关键途径的方法就是要拟定e[i]=L[i]的关键活动。假设以w[j,k]表达有向边<j,k>的权，即此边相应的活动所需的时间，为了求AOE网络中活动ai的最早开始时间e[i]和活动ai的最迟开始时间L[i]，先规定得顶点Vk的事件Vk的最早出现时间ev[k]和最迟出现时间Lv[k] 。
• ev[k]和Lv[k]可以采用下面的递推公式计算：
• (1) 向汇点递推
由源点的ev[1]=0开始，运用公式：

向汇点的方向递推，可逐个求出各顶点的ev 。式中p表达所有指向顶点的边的集合，如图5-6-6所示。

图5-6-6 集合p
此式的意义为：从指向顶点Vk的各边的活动中取最晚完毕的一个活动的完毕时间作为Vk的最早出现时间ev[k]。
• (2) 向源点递推
由上一步的递推，最后总可求出汇点的最早出现时间ev[n]。因汇点就是结束点，最迟出现时间与最早出现时间相同，即Lv[n]=ev[n]。从汇点的最迟出现时间Lv[n]开始，运用下面公式：

向源点的方向往回递推，可逐个求出各顶点的最迟出现时间Lv。式中s表达所有由Vj点指出的边的集合，如图5.6-7所示。

此公式的意义为：由从Vj顶点指出的各边所代表的活动中取需最早开始的一个开始时间作为Vj的最迟出现时间。
无论是向汇点递推还是向源点递推，都必须按一定的顶点顺序进行。
对所有的有向边，向汇点递推是先求出尾顶点的ev值，再求头顶点的ev值；向源点递推则相反，先求头顶点的Lv值，再求尾顶点的Lv值。
为此，可运用上节介绍的拓扑排序得到的顶点顺序进行向汇点的递推，向源点的递推按相反的顺序进行即可，不必再重新排序。
求关键途径的算法：
    (1)输入e条弧<j，k>，建立AOE-网的存储结构；
    (2)从源点v0出发，令ve[0]=0，按拓扑有序求其余各顶点的最早发生时间ve[i] (1≤i≤n-1)。假如得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键途径，算法终止；否则执行环节(3)。
    (3)从汇点vn出发，令vl[n-1]=ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i](n-2≥i≥0)；
    (4)根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间 l(s)。若某条弧满足条件e(s)=l(s)，则为关键活动。
    对图5-6-1例子中的AOE网络，各事件的最早出现时间和最迟出现时间及各活动的最早开始时间和最迟开始时间计算结果如表5.1所示。

表5-1 AOE网络中的关键活动
由表5-1可知时间余量为零的活动都是关键活动，即为a1，a4，a7，a8，a10，a11。
这些关键活动构成两条关键途径，即关键途径(V1，V2，V5，V7，V9)和(V1，V2，V5，V8，V9)。
在安排工程时，对于关键活动和余量小的活动应重点保证，余量较大的活动可适本地放松些，对非关键活动加速进行，并不能使整个工程提前完毕，只有提高关键途径上的活动的效率，才干缩短整个工程的工期。
例5.1已知一有向图的邻接表存储结构如图5-6-8所示，分别给出从顶点v1出发进行深度优先和广度优先遍历所得到的顶点序列。

图5-6-8 一个有向图的邻接表
【解答：】根据有向图的深度优先遍历算法，从顶点v1出发所得到的顶点序列是：
v1，v3，v4，v5，v2
根据有向图的广度优先遍历算法，从顶点v1出发所得到的顶点序列是：
v1，v3，v2，v4，v5
例5.2
有n个顶点的无向图或有向图采用邻接矩阵和邻接表表达，请回答下列问题:
(1) 如何计算图中有多少条边？
(2) 如何判断任意两个顶点i和j是否有边相连？
(3) 如何计算任意一个顶点的度是多少？

【解答】
解：(1) 对于无向图邻接矩阵中“1”的个数除2为图的边数。邻接表中的各单链表中的结点数除2为图的边数。
对于有向图邻接矩阵中“1”的个数为图的边数。邻接表中的各单链表中的结点数为图的边数。
(2) 对于无向图，在邻接矩阵中第i行第j列元素为“1”，或者第j行第i列元素为“1”，则顶点i与j有边相连。在邻接表中的第i个单链表中有结点为j，或者第j个单链表中有结点为i，则顶点i与j有边相连。
对于有向图，在邻接矩阵中第i行第j列元素为“1”，则有一条从i到j的边。在邻接表中的第i个单链表中有结点为j，则有一条从i到j的边。
(3)对于无向图邻接矩阵中第i行的元素之和为i顶点的度，邻接表中的第i个单
链表中的结点数为i顶点的度。
对于有向图邻接矩阵中第i行元素之和为i顶点的入度，第j列元素之和为j顶点的出度。在邻接表中，第i个单链表的结点数就是i顶点的出度，整个邻接表中具有的结点为i的结点数就是i顶点的入度。