【精品数据结构】拓扑排序.PPT.PPT

《【精品数据结构】拓扑排序.PPT.PPT》由会员分享，可在线阅读，更多相关《【精品数据结构】拓扑排序.PPT.PPT（54页珍藏版）》请在三一文库上搜索。

1、1,6.6 拓扑排序,目的 根据结点间的关系求得结点的一个线性排列。 在有关工程进度/次序规划之类问题中，有着大量应用。 一般的大型工程，都可以划分为多个工序/步骤/子工程，这些工序有的可独立进行，但大多数和其他工序关联，即某工序的进行，要等到其他一些工序的完成才能开始。这类问题都可归结到拓扑排序。,2,6.6.1 拓扑序列与AOV网,对有向图G，若它的一个结点序列 LS：v1, v2,., vn 满足这样的条件：是G的边时，在LS中vi位于vj之前（即ij），否则在LS中vi与vj的前后次序任意，则称LS为图G的一个拓扑序列，求拓扑序列的操作称为拓扑排序（Topological Sortin

2、g）。,某一图的拓扑序列可能不唯一,3,6.6.1 拓扑序列与AOV网,拓扑排序主要用在一类称为AOV网（Activity on Vertex networks）的有向图中。 AOV网是给有向图的结点与边赋予一定的语义的图，具体地： 结点代表活动。如工程中的工序/子任务、状态等 边代表活动之间的进行次序。边表示活动i先于j进行。 AOV网常用来表达流程图，如一个工程中各子任务间的流程图、产品生产加工流程图、程序流程图、信息（数据）流程图、活动安排流程图等,4,6.6.1 拓扑序列与AOV网,学生的选课次序就是一个AOV网应用问题。例如， 假定某计算机专业的主要课程如表 62所示，则对应的AOV

3、网如图 61所示。,图 对应的AOV网,5,6.6.1 拓扑序列与AOV网,图 61可有多个拓扑序列，下面给出了它的两个不同的拓扑序列： 1 2 3 4 6 5 9 7 8 11 1 2 3 4 6 5 7 9 8 11 如果采用串行修课方式，则可完全按拓扑序列进行，但往往是一段时间内需同时修多门课，这就需识别出哪些课可同时修，这是一个识别可并行成份的问题。例如，在图 61中，可并行的课程有(1,2,3)(4,6,10) (5) (9,7) (8,11)等几组。,图 对应的AOV网,6,6.6.2 拓扑排序算法与实现,(一）基本方法 进行拓扑排序的基本方法是简单而直观的，其包含下列几个步骤：

4、1 从有向图中找一个没有前趋的结点v，若v不存在，则表明不可进行拓扑排序（图中有环路），结束（不完全成功）； 2 将v输出； 3 将v从图中删除，同时删除关联于v的所有的边 4 若图中全部结点均已输出，则结束（成功），否则转1继续进行。,7,6.6.2 拓扑排序算法与实现,(一）基本方法 通过对此方法做适当扩充，就可在求拓扑序列的过程中标识出可并行活动（结点）。 具体做法是，初始时将所有无前趋结点标为一组可并行结点。然后，每次执行步骤3后，将新产生的无前趋结点标为新的一组可并行结点。为了将同组并行结点连续排列，在步骤1中应优先选取并行组号与上次选择结点的并行组号相同的结点（若有的话）,8,6.

5、6.2 拓扑排序算法与实现,(二）数据结构的选取 邻接表的图结点的定义修改为： template struct TGrphNode long nodeIdx; /结点编号 TElem nodeInfo; /结点信息 long inDegree; /结点的入度 TGrphEdge * firstOutEdge; /第一条出边的指针 ;,9,6.6.2 拓扑排序算法与实现,(二）数据结构的选取 而图边的定义仍为： template struct TGrphEdge long edgeEndIdx; /边终点编号 TEdgeInfo edgeInfo; /边信息 TGrphEdge *next; /

6、链指针 ;,10,6.6.2 拓扑排序算法与实现,(二）算法实现 for (每个结点v) if (v入度为0) v进栈; while (栈不空) 从栈中弹出一个元素送v; 输出v; 求出v的第1个直接可达邻接点w; while (w存在) 将w的入度域减1; if (w的入度域为0)w进栈; 求出v的下个直接可达邻接点w; /while /while,11,(二）算法实现 下面是具体的C+程序。 long TopoSort(TGrphNode *g, long n, long *resu) /对图g求拓朴序列，存入sesu(结点编号)，n为图结点数目。 /返回所求得的结点数。若返回值小于n，则

7、表示未能完全拓扑排序。 long *s, top, k, i; TGrphEdge *p; s = new longn+1; top=0; k=0; for (i=0; i=n; i+) if (gi.inDegree = 0) top+; stop=i; ,12,(二）算法实现 while (top0) i=stop; top-; resuk=i; k+; p=gi.firstOutEdge; while ( p!=NULL ) i=p-edgeEndIdx; gi.inDegree-; if (gi.inDegree=0) top+; stop=i; p=p-next; /while (p

8、!= delete s; return k; ,时间复杂度为O(n+m),13,6.7 AOE网与关键路径,求关键路径是对边加权的有向图的一种操作。 AOE网与AOV网类似，也是一种被赋予了抽象语义的有向图，是许多实际问题的模型。,14,6.7.1 AOE网与关键路径的概念,(一）AOE网 如果将有向图的结点与边按下列所述赋予抽象意义，则该种有向图就称为AOE网(Activity On Edge network) 边（弧）：代表活动（操作）； 边权：代表活动的持续时间。记边ak=的权为len(ak)或len(i,j)； 结点：代表事件（状态）。它表示它的各入边代表的活动均已完成，而它的出边代表

9、的活动可以开始。 AOE网中没有入边的结点称为始点，没有出边的结点称为终点。,15,AOE一般用来描述工程进度，结点表示工程进展中的状态，边表示子任务。图 61就是一个AOE网，它可以看作是一个具有11项子任务和9个状态的假想工程的进度图,16,6.7.1 AOE网与关键路径的概念,(二）AOE网的操作 针对AOE网的操作一般有下列几种: 关键路径CPM(Critical Path Method)。 这种操作最早用于维修与建筑行业中工期进度估算。 性能估计与复审PERT(Performance Evaluation and Review Technique)：该项操作最初是为了研制北极星式导弹

10、系统而引入的 资源分配与多工程调度RAMPS(Resource Allocation and Multi-Project Scheduling),17,6.7.1 AOE网与关键路径的概念,(三）关键路径的若干基本概念 下面的阐述中，设AOE网的起点为v0终点为vn 1关键路径 AOE网中，从事件i到j的路径中，加权长度最大者称为i到j的关键路径（Critical Path）。记为cp(i,j).特别地，始点0到终点n的关键路径cp(0,n)是整个AOE的关键路径。 显然，关键路径决定着AOE网的工期，关键路径的长度就是AOE网代表的工程所需的最小工期。,18,6.7.1 AOE网与关键路径的

11、概念,(三）关键路径的若干基本概念 2事件最早/晚发生时间 事件vi的最早发生时间ve(i)定义为：从始点到vi的最长（加权）路径长度，即cp(0,i) 事件vi的最晚发生时间vl(i)定义为：在不拖延整个工期的条件下，vi的可能的最晚发生时间。即 vl(i) = ve(n) - cp(i, n),19,6.7.1 AOE网与关键路径的概念,(三）关键路径的若干基本概念 3活动最早/晚开始时间 活动ak=的最早开始时间e(k)：等于事件vi的最早发生时间，即 e(k) = ve(i) = cp(0, i) 活动ak=的最晚开始时间l(k)定义为：在不拖延整个工期的条件下，该活动的允许的最迟开始

12、时间，即 l(k) = vl(j) len(i, j) 这里，vl(j)是事件j的允许的最晚发生时间，len(i, j)是ak的权。 活动ak的最大可利用时间：定义为l(k)-e(k),20,6.7.1 AOE网与关键路径的概念,(三）关键路径的若干基本概念 4关键活动 若活动ak的最大可利用时间等于0（即(l(k)=e(k)），则称ak 为关键活动，否则为非关键活动。 显然，关键活动的延期，会使整个工程延期。但非关键活动不然，只要它的延期量不超过它的最大可利用时间，就不会影响整个工期。,21,6.7.1 AOE网与关键路径的概念,(三）关键路径的若干基本概念 关键路径的概念，也可以用这里的关

13、键活动定义，即有下面的： 定理 62 某路径为关键路径的充分必要条件是，它上的各活动均为关键活动。,22,6.7.2关键路径的识别,(三）关键路径的若干基本概念 进行关键路径分析，目的是寻找合理的资源调配方案（这里的资源是指能使活动进行的人力或物力），使AOE网代表的工程尽快完成。 只有缩短关键路径上的活动（关键活动）才有可能缩短整个工期 识别关键路径的公共点就变得很重要,23,6.7.2关键路径的识别,(一）基本算法 设图G=(V, E)是个AOE网，结点编号为1,2,.,n，其中结点1与n 分别为始点和终点，ak=E是G的一个活动。 根据前面给出的定义，可推出活动的最早及最晚发生时间的计算

14、方法： e(k) = ve(i) l(k) = ve(j) - len(i,j),24,6.7.2关键路径的识别,(一）基本算法 结点的最早发生时间的计算，需按拓扑次序递推 ve(1) = 0 ve(j) = MAX ve(i)+len(i, j) 对所有 E的i,25,6.7.2关键路径的识别,(一）基本算法 结点的最晚发生时间的计算，需按逆拓扑次序递推： vl(n) = ve(n) vl(i) = MINvl(j) - len(i, j)对所有E的j,26,6.7.2关键路径的识别,(一）基本算法 这种计算方法， 依赖于拓扑排序 计算ve( j) 前，应已求得j 的各前趋结点的ve值，而计

15、算vl(i)前，应已求得i的各后继结点的vl值。 ve的计算可在拓扑排序过程中进行，即在每输出一个结点i后，在删除i的每个出边（即入度减1）的同时，执行 if ( vei+len(i,j) vej ) vej = vei + len(i,j),27,6.7.2关键路径的识别,(一）基本算法 通过逆方向使用拓扑序列即可递推出各vl的值，假定拓扑序列是topoSeq，则vl 的值的求法为（结点编号为1n）。 for (k=1; k=1; k-) i=topoSeqk; j=（i的第1个直接射出点）; while (j存在) if (vlj-len(i,j)vli) vli=vlj-len(i,j)

16、; j = （i的下一个直接射出点）; ,28,6.8最短路径,路径问题是有向图及无向图中的另一基本问题，它涉及下列两点： 对图中任两结点u与v，它们之间有路径吗？ 若u到v之间有不止一条路径，那么，哪一条是最短路径（代价最小路径）？ 对路径问题，有两个著名算法， Dijkstra 单源最短路径算法 Floyd每对结点最短路径算法。,6.8.1 路径问题,29,(一）基本方法 Dijkstra单源最短路径算法是求图中任一结点到其余各结点的最短路径（路径表示与长度）。,6.8.2Dijkstra单源最短路径算法,30,(二）基本策略 设图共有n个不同的结点，则从某一点出发达到其他各点的最短路径有

17、(n-1) 条 Dijkstra的基本策略是，按长度不减次序构造这(n-1)条最短路径，即先求出长度最小的一条最短路径，然后求出长度第二小的最短路径，最后求出长度最大的最短路径,6.8.2Dijkstra单源最短路径算法,31,例如，对图 61所示有向图，若求结点1到其它各结点的最短路径，则求得的次序为：1-2, 1-3, 1-5, 1-6, 1-4, 1-7.,图 有向图的单源最短路径,(a) 一个有向图,(b) 有向图(a)中1到其他各点的最短路径,32,(二）基本策略 另外，设立两种数据结构： 1.集合s：存放当前已找出的各最短路径的终点。即若vs，则表示始点到v的 最短路径已被求出 2

18、.路径数组dist：它的含意为： 若i s，则disi等于始点v0到i的距离 若i不属于s，则disi等于始点v0到i的中间只经过s中元素，且长度最小的路径的长度（若无此种路径，则视长度为） 这两个数据结构是生成最短路径的关键。其中dist充当候选集,6.8.2Dijkstra单源最短路径算法,33,Dijkstra单源最短路径算法及其正确性均基于下列几点事实。 (1)如果下一条（即长度递增序列中的下一条）最短路径的终点是u，则这条路径是从起点v0开始，中间只经过s中结点，而最后到达u的路径。 (2)从v0出发的长度最小的最短路径，必为v0的出边中权值最小者。 (3)下一条最短路径的终点u，必

19、定是尚未进入s中的那些结点u1,.,um对应的distu1,.,distum中值最小者所对应的那个uk，即u必满足： distu=mindistw，其中ws。,6.8.3Dijkstra算法的正确性,34,（一）算法实现基本框架 Dijkstra(g, n, v0, dist) /对图g求从源点v0到其余各点的最短路径，结果存于dist中。n为图中结点个数 根据g与v0初始化dist与s; while (未完) 求满足distu=MINdistw的u，这里ws; 将u加入到集合s中; 调整候选集dist /Dijkstra,6.8.4Dijkstra算法实现,35,（一）算法实现基本框架 根据

20、s与dist的定义，在初始时，令s只含源点v0，而对每个vv0，置distv为v0到v的边的权值（v0到v无边时置为） 将新造出的结点u加入s后，某些结点的dist值可能变得不满足dist的定义，故应调整dist，使它重新满足定义 调整的方法为 for (每个不在s中的w) if (distu+cost(u,w) distw ) distw=distu+cost(u,w);,6.8.4Dijkstra算法实现,36,6.8.4Dijkstra算法实现,37,（二）数据结构设计 (1) 图：输入量，为待求最短路径的图。根据Dijkstra算法的特点，采用邻接矩阵为好。具体定义如下： 边的权值：若

21、i到j有边 gij = ：若i到j无边,6.8.4Dijkstra算法实现,38,（二）数据结构设计 (2) 路径与候选集dist 为了能同时得到最短路径的构成（即路径上的结点序列），这里对dist作适当的扩充，使得能从它得到各最短路径的结点序列 源点v0到任一点u 的最短路径构成形式为下列两种情形之一： (v0,u)或 (v0,u1,., uk, u)(k1) 其中，路径(v0,u1,.,um)为v0到um的最短路径(1mk) 亦即，最短路径上结点序列的任一最左子序列均为某结点的最短路径结点序列 我们称(v0,u1,.,uk)或(v0)为v0到u 的最短路径的前趋路径,6.8.4Dijkst

22、ra算法实现,39,（二）数据结构设计 最短路径的此性质启发我们，对任一结点u，只需设立它的前趋路径的指示器就可推出源点到它的最短路径结点序列 据此，我们为dist 的元素增设一个pre字段，令它存放对应结点的前趋路径的终点编号，即disti.pre的值为源点到i的最短路径的前趋路径的终点编号 该字段相当于一个链指针，顺着它搜索的结果是最短路径的结点的逆序,6.8.4Dijkstra算法实现,40,（二）数据结构设计,6.8.4Dijkstra算法实现,41,（二）数据结构设计 (3) 集合s 集合s为中间量，用一维数组表示，其元素含意为： 若i！s：si=0 若is：si=1 如果图g邻接矩

23、阵的对角线元素不使用，则也可用对角线元素gii充当si。,6.8.4Dijkstra算法实现,42,（三）算法程序 struct TDijkPath float len; long pre; ;,6.8.4Dijkstra算法实现,43,6.8.4Dijkstra算法实现,long DijkstraPath(TGrphEdge *g, long n, long v0, TDijkPath *dist) char *s; long i, j, k; float minW; s = new charn+1; for (i=1; in; i+) /初始化 si = 0; disti.len = gv

24、0i; if (disti.len !=无边标志) disti.pre = v0; else disti.pre = -1; /表示不存在 /for sv0 = 1; /将源点v0放入s,44,6.8.4Dijkstra算法实现,for (i=1; in; i+) /每次求出一条最短路径 k=1; for (j=k+1; jn; j+) /求下条最短路径 if (sj ) if (distj.len distk.len) k=j; sk = 1; /将k加入s,45,6.8.4Dijkstra算法实现,for (j=1; jn; j+) /调整候选集 if (!sj) if (distk+gk

25、j distj ) distj = distk+gkj; distj.pre = k; /将k的前驱路径改为k /for (i=1; ) detele s; return n; ; / DijkstraPath,46,6.8.4Dijkstra算法实现,for (j=1; jn; j+) /调整候选集 if (!sj) if (distk+gkj distj ) distj = distk+gkj; distj.pre = k; /将k的前驱路径改为k /for (i=1; ) detele s; return n; ; / DijkstraPath,算法的时间复杂度为O(n2),47,48,

26、6.8.5 Floyd每对顶点间最短路径,Dijkstra单源最短路径算法每次只求一个源点到其余各点间的最短路径，若要求每对顶点间的最短路径，则需调用n次Dijkstra算法，时间复杂度为O(n3) 但对此问题，Floyd发现了一个更为直接的算法，我们称之为Floyd每对顶点间最短路径，它的时间复杂度也是O(n3),49,6.8.5 Floyd每对顶点间最短路径,（一）基本方法 Floyd算法实质上是一种迭代法，它在图的邻接矩阵上做n次迭代 第n 次迭代后，邻接矩阵i行j列上元素值即为i到j的最短路径值 具体地讲，Floyd 算法递推地产生一个矩阵序列（逻辑上）。 A1, A2, ., An

27、其中,A0=g（即图的邻接矩阵），Akij表示结点i到j的中间结点序号不大于k的最短路径长度(k=1,.,n) 显然，Anij是i到j的最短路径长度，因为它中间经过的结点没受限制（即允许为1n） 事实上，对每个k，Akij都表示i到j的最短路径长，但该最短路径有个条件限制：中间结点序号不大于k。随着k的增大，条件越来越放宽（对中间结点限制越来越少），直至k=n时，限制完全取消。,50,6.8.5 Floyd每对顶点间最短路径,（一）基本方法 现在讨论一下如何递推Ak 从i到j中间结点序号不大于k的最短路径有两种情况： (1)中间不经过结点k，那么有 Akij=Ak-1ij (2)中间经过结点k

28、：此时有 Akij Ak-1ij 对这后一种情况，该路径有两段连成，一段是i到k的中间结点序号不大于(k-1)的最短路径， 其长度为Ak-1ik；另一段为k到j的中间结点序号不大于(k-1)的最短路径， 其长度为Ak-1kj,51,6.8.5 Floyd每对顶点间最短路径,（一）基本方法 因此有 Akij = Ak-1ik+Ak-1kj 至于如何识别是属于情况(1)还是(2)，只要判别 Akij Ak-1ik+Ak-1kj 是否成立，若成立，则属于情况(2)，否则属于情况(1),52,（二）算法实现 void FlordPath(TGrphEdge *g, long n, float *A,

29、long *path) /g-输入量，表示图的邻接矩阵。n-图结点个数； /A-输出量，规模同g的二维数组，存放各对顶点间的最短路径的值； /path-输出量，规模同g的二维数组，为各对顶点间的最短路径的结点序列的链接。 long i, j, k; for (i=1; i=n; i+) for (j=1; j=n; j+) Aij = gij; if (Aij 最大权值) pathij = i; else pathij = -1; ,53,（二）算法实现 for (k=1; k=n; k+) for (i=1;i=n; i+) for (j=1; j=n; j+) if (Aik + Akj Aij ) Aij = Aik + Akj; pathij = pathkj; ,54,