数据结构 第二十讲拓扑排序

《数据结构 第二十讲拓扑排序》由会员分享，可在线阅读，更多相关《数据结构 第二十讲拓扑排序（49页珍藏版）》请在金锄头文库上搜索。

1、第二十讲 拓扑排序,一、有向无环图的定义 一个无环的有向图称做有向无环图（directed acycline graph），简称DAG图， 我们一般使用有向无环图来描述含有公 共子式的表达式的有效工具，利用它可以,实现对相同子式的共享，从而节省存储空 间。 例如:表达式的二叉树表示 (a+b)*(b*(c+d)+(c+d)*e)*(c+d)*e) 有些子表达式如(c+d)和(c+d)*e重复出 现，可利用有向无环图，实现共享。,*,+,*,+,*,b,a,e,+,d,c,*,d,c,+,b,*,e,+,d,c,*,+,+,*,b,a,*,*,e,+,d,c,对于无向图来说，若深度优先搜索遍历过

2、 程中遇到回边，则必定存在环；而对于有向图 来说，这条回边有可能是指向深度优先生成森 林中另一棵生成树上顶点的弧。但是，如果从,有向图上某个顶点v出发的遍历，在dfs(v)结 束之前，出现一条从顶点u到顶点v的回边， 由于u在生成树上是v的子孙，则有向图中必 定存在包含顶点v和u的环。,有向无环图也是描述一项工程或系统的进 行过程的有效工具，所有的工程都可以分为若 干个称做活动的子工程，而这些子工程之间， 通常受着一定条件的约束，如其中的某些子工 程必须在另一些子工程完成之后。,对整个工程和系统，人们关心的是两方面 的问题： 一、是工程能否顺利进行； 二、是估算整个工程完成所必须的最短时间 对

3、应于有向图，即为进行拓扑排序和关键 路径的操作，下面重点介绍拓扑排序。,二、拓扑排序,1、定义 由某个集合上的一个偏序得到该集合 上的一个全序，这个操作称为拓扑排序。 2、AOV网 一般情况下，在有向图中，若用顶点来,表示“活动”，边表示活动间的先后关系，这种 顶点活动网（activity of vertex network） 简称AOV网。 假设计算机专业学生要修完课程才能毕 业，此时，工程就是学生毕业（修完教学计 划的课程），而“活动”就是学习一门课程。,构造上述课程的AOV网如下：,c2,c1,c3,c4,c6,c7,c5,c8,图 1,在AOV网中，若顶点i和j之间存在一条有 向路径，

4、则称顶点i是顶点j的前驱，或称顶点 j是顶点i的后继。若是AOV网中的一条 弧，则称i是j的直接前驱，或称j是的直接后 继。C1,C2是C3的直接前驱；C7是C3的直,接后继；C1，C2也是C7的前驱，但是不是 直接前驱。可见，在AOV网中，弧所表示的 优先关系具有传递性。 在AOV网中不应该出现有向回路，若存 在回路，则说明某项“活动”的完成是以自身,任务的完成为先决条件的，显然，这样的活 动是不可能完成的。 一个工程是否可行，首先，就是要看它 在AOV网中是否存在回路。检查AOV网中是否 存在回路的方法就是拓扑排序。,3、拓扑排序,在AOV网中，若从Vi到Vj有一条路径，则在 该序列中Vi

5、必在Vj的前面。即对于一个AOV 网，构造其所以顶点的线性序列，使此序列不 仅保持网中各顶点间原有的先后关系，而且使 原来没有先后关系的顶点也人为地建立起先后 关系，这样的线性序列称为拓扑序列。构造 AOV网的拓扑序列的操作称为拓扑排序。,拓扑排序的性质 其一、拓扑排序序列不一定唯一,2,1,3,4,5,6,序列1：1-2-3-4-6-5 序列2：1-4-2-3-6-5,图 2,其二：AOV网中不一定都有拓扑排序。 在AOV网中，任何部分的子图不能够有回 路，这是AOV网存在拓扑序列的前提。 如果存在回路，就意味某项活动应该以自 己为先决条件，显然这是不可能的。我们称 在AOV网中存在回路的现

6、象为死锁现象，它 将使程序的流程出现一个死循环。,所以判断AOV网中是否存在有向回路。也就 是判断AOV网所描述的工程是否可行，即AOV网 中是否有拓扑排序序列存在。,4、拓扑排序的步骤和方法 （1）在网中选择没有前趋（即入度为0）的 顶点且输出。,（2）从网中删去该顶点，并且删去从该顶 点出发所有的边（即该顶点的所有直接后继 顶点的入度都减1）。 （3）重复以上两步，直到网中不存在入度 为0的顶点为止。,这种操作的结果有两种： 一种是网中全部的顶点均被输出，说明网中不存在回路； 另一种情况就是未输出网中的所有顶点，网中剩余的顶点均有前驱，这就说明网中存在有向回路。 下面我们介绍一下图2的拓扑

7、排序的生成过程。,2,1,3,4,5,6,（a）Aov网,2,3,4,5,6,（b）输出顶点1后,2,3,5,6,（c）输出顶点4后,3,5,6,（d）输出顶点2后,5,6,（e）输出顶点6后,5,（f）输出顶点5后,得到拓扑序列为： 1-4-2-3-6-5,注意：网中不存在回路，说明该网所表示 的工程项目是可行的。,当用计算机进行拓扑排序时首先解决 AOV网的拓扑排序问题，可以选择邻接表 作为网的存储结构。为了检查每个顶点的 入度，我们在顶点表中增加一个入度域id，,以表示各个顶点当前的入度值，可以通过邻接 表动态生成的过程累加得到如图2，AOV网的 邻接表如图3。,在具体实现算法的时候，链

8、栈无需占用 存储空间，而是利用顶点表中值为0的id域 来存放链栈中的指针。利用顶点表中的顶点 vertex来作为链栈的顶点域。,1,2,3,4,5,6,vex,next,图 3,算法描述如下：,typedef int datatype; typedef int vextype; typedef struct arcnode int adjvex; /邻接点域 struct node *nextarc; /链域 arcnode; /边表结点,typedef struct vextype vertex; /顶点信息 int id; /入度 arcnode *firstarc; /边表头指针 vno

9、de; /顶点表结点 vnode dign; /全程量邻接表,TOPOSORT（vnode dig） int i,j,k,m=0,top=-1; arcnode *p; for(i=0;in;i+) /建立入度为0的栈 if(digi.id=0) digi.id=top; top=i; ,while(top!=-1) /栈非空 j=top; top=digi.id; /栈顶元素退栈 printf(digj.vertex); /输出退栈顶点 m+; /输出顶点计数 p=digj.firstarc;,while(p) /删去从该顶点出发的弧 k=p-adjvex; digk.id-; if(dig

10、k.id=0) digk.id=top; top=k; ,p=p-nextarc; /找下一条邻接边 if(mn) printf(“n the network has a cyclen”); /TOPOSORT,分析上述算法，设AOV网有n个顶点和e条 边，初始建立入度为0的顶点栈，检查所有顶 点一次，执行时间为O(n)；排序中若AOV网无 回路，则每个顶点入、出栈各一次，每个边表 结点被检查一次，执行时间是O(n+e)。所以总 的时间复杂度为O(n+e)。,三、关键路径 对于一项工程，我们可以将其表示成一个 AOV网。通过对其进行拓扑排序即可得到一种 或几种可行的方案。而对于一项工程，若想计

11、 算完成整个工程需要多少天以及哪些活动是影 响工程进度的关键时，我们就可以通过AOE网 来解决。,若在带权有向图中，用顶点表示事件，有向 边表示活动，边上的权值表示该活动所需的时 间，则此带权有向图称为用边表示“活动”的网 (activity on edge network)简称AOE网。,通常，AOE网上列出了完成预定工程计划 所需要进行的活动。可用来估算工程的完成 时间，确定哪些活动是影响工程工期的关键， 并进行安排、调度以缩短整个工程的工期。 在用AOE网表示一项工程的施工计划时， 顶点表示的事件实际上就是某些活动已经完,成或另一些活动可以开始的标志。即顶点所 表示的事件实际上就是它的入

12、边所表示的活 动均已完成以及它的出边所表示的活动均可 以开始的一种状态。 整个工程只有一个开始点和一个完成点， 在正常情况下，网中只有一个入度为零的点 (源点)和一个出度为零的点(汇点)。,V1,V2,V3,V4,V5,V7,V9,V8,V6,源点,汇点,a1=6,a2=4,a5=1,a4=1,a7=9,a8=7,a10=2,a11=4,a9=4,a6=2,a3=5,图 AOE网,和AOV网不同，对AOE网有待研究的问题 是： (1) 完成该项工程至少需要多少时间？ (2) 哪些活动是影响工程进度的关键？ 在AOE网中，有些活动是可以并行完成 的，所以整个工程的最短时间应该是从源点到 汇点的最

13、长路径长度。,我们把从源点到汇点的最长路径长度称为关 键路径。关键路径上的活动称为关键活动。 定义几个相关变量，并说明其计算方法。 (1) 顶点事件的最早发生时间Ve(j) Ve(j)是指从源点V1到Vj的最长路径长度。 这个时间决定了所有从Vj发出的弧所表示的,活动能够开工的最早日期。其计算方法如下： Ve(1)=0 Ve(j)=maxVe(i)+dut() T,2jn 其中，T是所有到达顶点j的弧的集合；n 是网 中的顶点数；dut()是弧的权值。,(2) 顶点时间的最晚发生时间Vl(i) Vl(i)是指在不拖延整个工程工期的情况 下，事件Vi所允许的最晚发生时间。对一个 工程来说计划用几

14、天完成可以从AOE网中求 得。其数值就是汇点Ve的最早发生时间Ve(n), 而这个时间也就是Vl(n)。其它顶点的最晚发,生时间都应从汇点开始，逐步向源点方向递 推才能求得，Vl的计算公式如下： Vl(n)=Ve(n) Vl(i)=minVl(j)-dut() S 其中S是所有从顶点i发出的弧的集合。,(3) 边活动的最早开始时间Ee(i) Ee(i)是指该边所表示的活动ai最早可以开 始的时间。若活动ai由弧表示，则 Ee(i)=Ve(j) 这说明活动ai的最早开始时间等于事件Vj的 最早发生时间。,(4) 边活动的最晚开始时间El(i) El(i)是指在不推迟整个工程工期的情况 下，允许该活动最晚开始的时间。 若活动ai由弧表示，则 El(i)=Vl(k)-dut(),对于活动ai来说，若Ee(i)=El(i)，则表示该活 动的最早开工时间与整个工程计划允许的该 活动的最晚开始时间相同。 若ai活动不能按计划日期完成，则整个工 程就要延期。若它提前完成，整个工程也可 能提前完成，这个活动就是关键活动。,V1,V2,V5,V8,V7,V9,4,6,2,9,7,1,