图的拓扑排序关键路径和生成树

数据结构与算法分析

第11章

图

拓扑排序Topological Sort (1)问题: 给定一组有先决条件约束的工作、课程等, 希望 以某种线性顺序组织这些任务，且不违反任何的先 决条件.

可以用一个有向无环图(DAG)来模拟这个问题。因为 任务之间存在先决条件关系，即顶点之间有方向性， 因此图是有方向的。图又需要是无回路的，因为回 路中隐含了相互冲突的条件，从而使某些条件不可 能在不违反任何先决条件的情况下得到实现.将一个DAG中所有顶点在不违反先决条件规定的基 础上排成线性序列的过程称为拓扑排序2

拓扑排序 (2)

由此所得顶点的线性序列称之为 拓扑有序序列例如：对于下列有向图B A C D

可求得拓扑有序序列： ABCD 或 ACBD5

反之，对于下列有向图BA C D

不能求得它的拓扑有序序列。 因为图中存在一个回路 {B, C, D}6

如何进行拓扑排序？一、从有向图中选取一个没有前驱 的顶点，并输出之；

二、从有向图中删去此顶点以及所 有以它为尾的弧； 重复上述两步，直至图空，或者 图不空但找不到无前驱的顶点为止。7

c a g b h f d e

a

b h c d g f

e

在算法中需要用定量的描述替代定性的概念没有前驱的顶点 入度为零的顶点 删除顶点及以它为尾的弧 弧头顶点的入度减18

J1 J2

J3

J4

J5

J6

J7

0

10

10 0

22 1

22 1

11 0

11 1 1 0 0

打印J1打印J2 打印J3 打印J4 打印J5 打印J7

00

10 0

0

1 打印J6

使用队列对图11.1所示图进行拓扑排序，其顶点的打印顺序 将是J1,J2,J3,J6,J4,J5,J7 9

Queue-Based Topsortvoid topsort(Graph* G, Queue<int>* Q) { int Count[G->n()]; int v, w; for (v=0; v<G->n(); v++) Count[v] = 0; for (v=0; v<G->n(); v++) // Process edges for (w=G->first(v); w<G->n(); w = G->next(v,w)) Count[w]++; // Add to v2's count for (v=0; v<G->n(); v++) // Initialize Q if (Count[v] == 0) // No prereqs Q->enqueue(v); while (Q->length() != 0) { Q->dequeue(v); printout(v); // PreVisit for V for (w=G->first(v); w<G->n(); w = G->next(v,w)) { Count[w]--; // One less prereq if (Count[w] == 0) // Now free Q->enqueue(w); } } 10 }

拓扑排序 (3)void topsort(Graph* G) { // Topological sort int i; for (i=0; i<G->n(); i++) // Initialize G->setMark(i, UNVISITED); for (i=0; i<G->n(); i++) // Do vertices if (G->getMark(i) == UNVISITED) tophelp(G, i); // Call helper } void tophelp(Graph* G, int v) { // Process v G->setMark(v, VISITED); for (int w=G->first(v); w<G->n(); w = G->next(v,w)) if (G->getMark(w) == UNVISITED) tophelp(G, w); printout(v); // PostVisit for Vertex v }11

关键路径a1=6 V1

V2

a4=1 V5

a7=9

V7

a10=2 V9

a2=4V3

a5=1a3=5 V4

a8=7

V8 a9=4

a11=4

a6=2 V612

事件V1之前的活动就是以 V1 为头的弧表 示的活动， V1之后的活动是以V1为尾的弧表 示的活动。如 V5之前的活

动是a4, a5; V5之后 的活动是a7, a8 。

事件 V1 的发生表示 V1 之前的活动已完成，V1之后的活动可以开始，(但不一定马上开始)。 对此假想工程有：

13

a1=6 V1: 工程开始

V2

a4=1

V7 a7=9

a10=2

V1

a2=4

V5a5=1

V9 a8=7 V8 a9=4 a11=4

V2: a1完成, a4可以开始 V3: a2完成, a5可以开始 V4: a3完成, a6可以开始

V3 a3=5V4

a6=2 V6

V5: a4, a5完成, a7, a8可以开始V6: a6完成, a9可以开始 V7: a7完成, a10可以开始 V8: a8, a9完成, a11可以开始 V9: a10, a11完成, 即工程结束14

注： 工程开始，某些活动可以同时执行，但不一 定要同时执行。某一事件发生前，在它之后 的活动不能开始执行，(如v2, v3发生之前，a4, a5不能执行) 正常情况下，整个工程只有一个开始点和一 个完成点。在AOE网中

开始点：(即入度为零的点)称为源点完成点：(出度为零的点)称为汇点15

关键路径与AOV网不同。对AOE网要研究的问题是： 1) 完成整个工程至少需多少时间？

2) 哪些活动是影响工程进度的关键？

16

术语 关键路径(criticed path):从源点到汇点的最长路径叫关键 路径，其路径长度是该路径上活动持续时间之和. 也是工 程完成的最少时间. 事件最早发生时间：从源点到事件Vi的最长路径长度，称 为Vi的最早发生时间. 用Ve(i)表示. Ve(i)也决定了所有Vi 之后的活动的最早可以开始时间. 事件最迟发生时间：不影响整个工程进度，而Vi可最迟发 生的时间称为Vi的最迟发生时间. 用Vl(i)表示. 活动最早开始时间：活动ai最早可以开始进行的时间. 用e(i) 表示. 活动最迟开始时间：在不推迟整个工程完成的前提下，活 动ai最迟必须开始进行的时间，用l(i)表示. 关键活动：活动时间余量为0的活动. 即l(i) e(i)=0的活动. 关键路径上的所有活动都是关键活动. 非关键活动：不在关键路径上的活动.17