拓扑排序.ppt

拓扑排序.ppt

《拓扑排序.ppt》由会员分享，可在线阅读，更多相关《拓扑排序.ppt（46页珍藏版）》请在冰点文库上搜索。

数据结构与算法-第二十一讲,北方民族大学计算机科学与工程学院王伦津研究员,拓扑排序的概念以及算法实现,21、拓扑排序的概念以及拓扑排序的算法实现,掌握拓扑排序的概念，拓扑排序的算法与实现，学会在AOV和AOE网上的应用,目录,21.1拓扑排序21.1.1拓扑序列与AOV网21.1.2拓扑排序算法与实现21.2AOE网与关键路径21.2.1AOE网与关键路径的概念21.2.2关键路径的识别,21.1拓扑排序,拓扑排序是定义在有向图上的一种操作，目的是根据结点间的关系求得结点的一个线性排列（这点与遍历操作的目的类似）。

这种操作在有关工程进度/次序规划之类问题中，有着大量应用。

一般的大型工程，都可以划分为多个工序/步骤/子工程，这些工序有的可独立进行，但大多数和其他工序关联，即某工序的进行，要等到其他一些工序的完成才能开始。

这类问题都可归结到拓扑排序。

21.1.1拓扑序列与AOV网,对有向图G，若它的一个结点序列LS：

v1,v2,.,vn满足这样的条件：

是G的边时，在LS中vi位于vj之前，否则（不是边时）在LS中vi与vj的前后次序任意，则称LS为图G的一个拓扑序列，求拓扑序列的操作称为拓扑排序（TopologicalSorting）。

从代数结构角度来看，拓扑排序是由某集合上的一个偏序关系得到一个全序关系的操作。

若将集合中结点作为图结点，将它上的偏序关系作为图的边，则任一偏序关系均可表示为一个有向图。

显然，某一图的拓扑序列可能不唯一。

拓扑排序主要用在一类称为AOV网（ActivityonVertexnetworks）的有向图中。

AOV网是给有向图的结点与边赋予一定的语义的图，具体地：

结点代表活动。

如工程中的工序/子任务、状态等边代表活动之间的进行次序。

边表示活动i先于j进行。

AOV网常用来表达流程图，如一个工程中各子任务间的流程图、产品生产加工流程图、程序流程图、信息（数据）流程图、活动安排流程图等。

例211学生的选课次序就是一个AOV网应用问题。

假定某计算机专业的主要课程如图211（左）所示，则对应的AOV网如图211（右）所示。

图211（右）可有多个拓扑序列，下面给出了它的两个不同的拓扑序列：

12346105978111234610579811如果图中两个结点之间均没有通路，那么称它们是可并行的。

在一个拓扑序列中，如果某子串（序列中某一段）中的各结点之间均是可并行的，则称该段为一个并行段（组）。

一个可并行组包含了所有的可并行结点，则称该组为最大并行段（组）。

找出最大并行组的工作称为并行识别。

图211课程表（左）对应的AOV网（右）,并行组具有重要的实际意义。

位于同一组的各结点代表的活动可以同时进行，以缩短整个事务的完成时间。

例如，对选课问题，如果采用串行修课方式，则可完全按拓扑序列进行，但若要在一段时间内同时修多门课，这就需识别出哪些课可同时修，这是一个并行识别问题。

同一并行组内的课程可以同时修学。

例如，在图211中，可并行的课程组有（1,2,3）、（4,6,10）、（5）、（9,7）、（8,11）。

但注意，这些组之间还是有序的（这几个组的次序为它们的出现次序）。

并不是所有的有向图都可以进行拓扑排序。

显然，若图中每个结点都有前驱，或者每个几点都有后继，则该图是不可拓扑排序的。

21.1.2拓扑排序算法与实现,

（一）基本方法这里，我们给出一种拓扑排序算法。

该算法是简单而直观的，实质上属于广度优先遍历，因此称为广度优先拓扑排序算法。

该算法包含下列几个步骤：

1从有向图中找一个没有前趋的结点v，若v不存在，则表明不可进行拓扑排序（图中有环路），结束（不完全成功）；2将v输出；3将v从图中删除，同时删除关联于v的所有的边4若图中全部结点均已输出，则结束（成功），否则转1继续进行。

10,9,6,4,5,7,8,11,9,5,7,8,11,9,7,8,11,11,8,逐次去掉没有前趋的结点的过程,图21-2,课程表AOE网的邻接矩阵，它的列全为0的点，就是无前趋的点，取出该点,删除该点对应的列和行，矩阵的阶数减1，再发现新的全为0的列，同样办法处理，直至所有结点输出,11,增加一列，表示各点的入度,先扫描入度为0的结点，将其取出，然后删除与其有链接的边。

同时减少对应边终点的入度。

例中删除1、2、3点后结点4的入度减2为0，结点6的入度减1为0，结点9的入度减1，节电10的入度减3。

结点4、6、10成为新的入度为0的结点,此方法的正确性是显然的。

通过对此方法做适当扩充，就可在求拓扑序列的过程中标识出可并行活动（结点）。

具体做法是，初始时将所有无前趋结点标为一组可并行结点。

然后，每次执行步骤3后，将新产生的无前趋结点标为新的一组可并行结点。

为了将同组并行结点连续排列，在步骤1中应优先选取并行组号与上次选择结点的并行组号相同的结点（若有的话）。

U对拓扑排序，还有一种算法，称为深度优先拓扑排序。

它的基本思想是先输出无后继的结点，即对每个结点v，检查先一次递归地求出v的每个后继的拓扑序列（各序列连接在一起），然后将v插入到该拓扑序列的最前面。

关于具体的程序实现，留作练习。

（二）数据结构的选取为了方便拓扑排序的实现，需对前面介绍过的图的存贮结构做些扩充。

单纯从进行拓扑排序来讲，图采用邻接表较为方便，所以这里只考虑邻接表的情况。

从前面给出的拓扑排序基本方法看，拓扑排序涉及的基本操作有：

n判别某结点是否有前趋；n删除一个无前趋结点及其关联的边。

为此，我们为每个结点设一个入度域。

结点入度大于0时表示有前趋，否则无前趋。

对于删除，其真正目的也不是删除，而是为了通知出点：

对应的一个前驱已处理完。

因此，删除某结点时，只需对该结点的各直接可达邻接点（出点）的入度分别减1。

为了方便找到尚未输出的无前趋结点，将它们统一存放在一个栈中。

每次执行入度减1（即删除一边）操作后，若有结点入度变为0，则将它放入栈中。

每次选择无前趋结点时，也是从栈中提取。

为此，邻接表的图结点的定义中需设置入度域，我们将前面给出的TGraphNodeAL定义修改为：

templatestructTGraphNodeAL:

publicTGraphNode0/邻接表结点public:

GraphEdgeAL*firstOutEdge;/本结点的第一条出边的指针longinDegree;/入度/面是其他成员的声明，同TGraphNode0，此处不重载，故不给出;,根据上面的讨论，可给出拓扑排序算法的粗略描述：

longTopoSort（图g）longcnt=0;for（每个结点v）if（v入度为0）v进栈;while（栈不空）从栈中弹出一个元素送v;输出v;cnt+;求出v的第1个直接可达邻接点w;while（w存在）将w的入度域减1;if（w的入度域为0）w进栈;求出v的下个直接可达邻接点w;/while/whilereturncnt;,（三）算法实现,下面是具体的C+程序。

在该程序中，没有单独设置栈，而是利用结点数组g的入度域做栈。

templatelongTopoSort（TGraphNodeAL*g,longn,long*resu）/对图g求拓朴序列，存入resu（结点编号），n为图结点数目。

/返回所求得的结点数。

若返回值小于n，则表示未能完全拓扑排序。

longtop,cnt,i;TGraphEdgeAL*p;top=0;cnt=0;for（i=0;i=n;i+）if（gi.inDegree=0）gi.inDegree=top;top=i;/结点i进栈。

用g的入度域做为栈。

while（top0）i=top;top=gtop.inDegree;/出栈，栈顶元素送iresucnt=i;k+;p=gi.firstOutEdge;while（p!

=NULL）i=p-endNo;gi.inDegree-;if（gi.inDegree=0）gi.inDegree=top;top=i;/结点i进栈p=p-next;/while（p!

=returncnt;,U我们这里是为了方便才使用栈。

但使用栈不能识别并行成分。

事实上，拓扑排序可以使用队列，这样也可以方便地识别并行成分。

分析此算法的时间复杂度。

假定图的结点数与边数分别为n与m。

初始化操作是扫描n个结点，将入度为0者进栈，时间复杂度为O（n），此后是两个嵌套着的while循环，直接根据循环条件分析循环体进行的次数比较困难，故换个角度进行分析。

首先看进栈操作（及输出操作），因在无环情况下每个结点恰好进栈一次，故此操作有时间复杂度O（n）。

其次分析入度减1操作。

在无环情况下，当排序结束时，每个边恰好被逻辑删除一次，故入度减1操作的时间复杂度为O（m）。

因这几种操作是拓扑排序算法的主体。

故整个算法的时间复杂度为O（n+m）。

A如果入度域是做为公用的数据成员，则它的值应该一直保持正确。

但该程序运行后，入度域的值被改变了，故该程序有副作用！

避免的方法是设立临时结构存放入度值。

在上面给出的程序中，为了节省空间，我们没有单独设立栈，而利用图结点（其存放在称为头数组的数组中）中的入度域构造一个链式栈。

在拓扑排序程序中，逻辑上栈存放当前入度为0且尚未输出的结点，而这些结点的入度域此时对该程序已无用，所以可用它们形成一个链，将它们链接在一条链中，从而起到栈的作用。

具体实施方法是，对入度为0的结点，令它的入度域的值为下一个入度为0的结点在头指针数组中的序号（下标），最后一个入度为0的结点的入度域置特殊标志（如-1）（充当栈底），最先一个入度为0的结点的位置（在数组中的下标）用一个指示器指示（如top），充当栈顶指示器。

U这种栈实质上是一种静态链式栈。

这里给出的方法，不仅对拓扑排序本身有意义，更重要的是，它代表着一种方法。

（四）静态链栈的使用,入度,图213静态链式栈操作,（c）一次出栈后：

链栈为（3，1）,（b）初始化后：

链栈为（5，3，1）,（c）假定结点2入度变为0,进栈后栈为:

（2,3,1）,（a）初态：

结点（5,3,1）入度为0,下面给出具体的进栈和出栈操作方法。

设top中存放栈顶元素对应的数组下标，i是某个图结点的编号（与图数组下标兼容）。

1进栈：

结点i进栈：

gi.inDegree=top;top=i;入度2出栈：

栈顶元素送i：

i=top;top=gtop.inDdegree;图213给出了这种栈的进栈和出栈操作的例子。

U也可以类似地实现静态链队。

21.2AOE网与关键路径,求关键路径是对边加权的有向图的一种操作。

AOE（ActivityOnEdgenetwork）网与AOV网类似，也是一种被赋予了抽象语义的有向图，是许多实际问题的模型。

21.2.1AOE网与关键路径的概念,

（一）AOE网前面介绍过，对图结构，在实际应用时可给结点或边赋予某种描述量权，这里我们考虑边带权的有向图。

如果将有向图的结点与边按下列所述赋予抽象意义，则该种有向图就称为AOE网。

图214AOE网举例,l边（弧）：

代表活动（操作）；l边权：

代表活动的持续时间。

记边ak=的权为len（ak）或len（i,j）；l结点：

代表事件（状态）。

它表示它的各入边代表的活动均已完成，而它的出边代表的活动可以开始。

事实上，某结点代表的事件是它的各入边代表的活动的共同作用结果，同时也是它的各出边代表的活动的启动条件。

AOE网中没有入边的结点称为始点，没有出边的结点称为终点。

AOE一般用来描述工程进度，结点表示工程进展中的状态，边表示子任务。

图214就是一个AOE网，它可以看作是一个具有11项子任务和9个状态的假想工程的进度图。

v1,v2,v3,v4,a7=9,a9=4,a6=2,a5=1,a8=7,a4=1,a11=4,v9,a10=2,a11=4,v6,v8,v7,v5,v9,v7,v8,v9,对应邻接矩阵，这是一个上三角形矩阵,根据列查找无前趋的点,删除该点对应的行，即删除所连接的边,

（二）AOE网的操作针对AOE网的操作一般有下列几种:

l关键路径CPM（CriticalPathMethod）。

这种操作最早用于维修与建筑行业中工期进度估算。

l性能估计与复审PERT（PerformanceEvaluationandReviewTechnique）：

该项操作最初是为了研制北极星式导弹系统而引入的。

l资源分配与多工程调度RAMPS（ResourceAllocationandMulti-ProjectScheduling）,（三）关键路径的若干基本概念下面的阐述中，设AOE网的起点为v0终点为vn.1关键路径AOE网中，从事件i到j的路径中，加权长度最大者称为i到j的关键路径（CriticalPath），记为cp（i,j）。

特别地，始点0到终点n的关键路径cp（0,n）是整个AOE的关键路径。

显然，关键路径决定着AOE网的工期，关键路径的长度就是AOE网代表的工程所需的最小工期。

2事件最早/晚发生时间事件vi的最早发生时间ve（i）定义为：

从始点到vi的最长（加权）路径长度，即cp（0,i）事件vi的最晚发生时间vl（i）定义为：

在不拖延整个工期的条件下，vi的可能的最晚发生时间。

即vl（i）=ve（n）-cp（i,n）,3活动最早/晚开始时间活动ak=的最早开始时间e（k）：

等于事件vi的最早发生时间，即e（k）=ve（i）=cp（0,i）活动ak=的最晚开始时间l（k）定义为：

在不拖延整个工期的条件下，该活动的允许的最迟开始时间，即l（k）=vl（j）len（i,j）这里，vl（j）是事件j的允许的最晚发生时间，len（i,j）是ak的权。

活动ak的最大可利用时间：

定义为l（k）-e（k）4关键活动若活动ak的最大可利用时间等于0（即（l（k）=e（k）），则称ak为关键活动，否则为非关键活动。

显然，关键活动的延期，会使整个工程延期。

但非关键活动不然，只要它的延期量不超过它的最大可利用时间，就不会影响整个工期。

关键路径的概念，也可以用这里的关键活动定义，即有下面的：

定理72某路径为关键路径的充分必要条件是，它上的各活动均为关键活动。

证：

设v0与vn分别为AOE网的始点与终点。

用len（P）表示路径/边P的加权长度，先证必要性。

设cp（0,n）是一条关键路径，ak=是它上的任一个活动。

由前面的定义知，len（cp（0,n）=ve（n）len（cp（0,n）=len（cp（0,i）+len（ak）+len（cp（j,n）故len（cp（0,i）+len（ak）+len（cp（j,n）=ve（n），即len（cp（0,i）=ve（n）-len（cp（j,n）-len（ak）=vl（j）-len（ak）=l（k）又len（0,i）=ve（i）=e（k）从而e（k）=l（k）这表明，活动ak是关键活动。

必要性得证。

再考查充分性。

现假定某路径p（0,n）上各活动均为关键活动，但p（0,n）不是关键路径。

这样就有，len（p（0,n）考查之，显然len（p（0,n）=len（p（0,i）+len（ak）+len（p（j,n）故len（p（0,i）+len（ak）+len（p（j,n）ve（n）即len（p（0,i）ve（n）-len（p（j,n）-len（ak）=ve（j）-len（ak）=l（k）但len（p（0,i）=ve（i）=e（k）从而e（k）l（k）这与ak是关键活动矛盾，充分性亦得证。

21.2.2关键路径的识别,进行关键路径分析，目的是寻找合理的资源调配方案（这里的资源是指能使活动进行的人力或物力），使AOE网代表的工程尽快完成。

为此，需先识别关键路径。

只有缩短关键路径上的活动（关键活动）才有可能缩短整个工期。

如果存在多条关键路径，只缩短部分关键路径上的活动还不够，要能使各关键路径同时缩短才有效。

在这种情况下，识别关键路径的公共点就变得很重要，因为改变这些公共点的工期，可同时缩短多条关键路径，好钢用在了刀刃上。

这些问题都是以识别关键路径为基础的。

（一）基本算法关键路径算法是一种典型的动态规划法，这点在学了后面的算法设计方法后就会看到。

下面就来介绍该算法。

设图G=（V,E）是个AOE网，结点编号为1,2,.,n，其中结点1与n分别为始点和终点，ak=E是G的一个活动。

根据前面给出的定义，可推出活动的最早及最晚发生时间的计算方法：

e（k）=ve（i）l（k）=ve（j）-len（i,j）,结点的最早发生时间的计算，需按拓扑次序递推：

ve

（1）=0ve（j）=MAXve（i）+len（i,j）对所有E的i结点的最晚发生时间的计算，需按逆拓扑次序递推：

vl（n）=ve（n）vl（i）=MINvl（j）-len（i,j）对所有E的j关于ve与vl的求法，可参阅图215。

这种计算方法，依赖于拓扑排序，即计算ve（j）前，应已求得j的各前趋结点的ve值，而计算vl（i）前，应已求得i的各后继结点的vl值。

ve的计算可在拓扑排序过程中进行，即在每输出一个结点i后，在删除i的每个出边（即入度减1）的同时，执行if（vei+len（i,j）vej）vej=vei+len（i,j）实际上，该操作对i的每个后继j分别进行一次。

因此对程序作少量扩充即可求得ve。

vl的值可按类似的方法在逆拓扑排序过程（即直接按与拓扑序列相反的次序输出结点的过程）中求得，但一般不必专门这样进行。

事实上，通过逆方向使用拓扑序列即可递推出各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）;j=（i的下一个出点）;,求图21-6的AOE网的所有事件的最早发生时间ee（）；所有事件的最迟发生时间le（）；每项活动ai的最早开始时间e（）和最迟开始时间l（），完成此工程最少需要多少天？

那些是关键活动，是否存在某项活动，当其提高速度后能使整个工程缩短工期?

图21-6一个AOE网,完成此工程最少需要18天，关键活动为a1,a4,a7,a10和a1,a4,a8,a11,提高a1,a4的速度可缩短工期,所有事件的最迟发生时间le（）如下;,所有事件的最早发生时间ee（）如下;,ee

（1）=0;ee

（2）=6;ee（3）=4;ee（4）=5;ee（5）=max（ee

（2）+1,ee（3）+1）=7ee（6）=ee（4）+2=7ee（7）=ee（5）+9=16ee（8）=max（ee（5）+7,ee（6）+4）=14ee（9）=max（ee（7）+2,ee（8）+4）=18,le（9）=ee（9）=18le（8）=le（9）-4=14le（7）=le（9）-2=16le（6）=le（8）-4=10le（5）=min（le（7）-9,le（8）-7）=7le（4）=le（6）-2=8le（3）=le（5）-1=6le

（2）=le（5）-1=6le

（1）=min（le

（2）-6,le（3）-4,le（4）-5）=0,求所有活动的最早开始时间e（）和最迟开始时间l（）,活动a1:

e

（1）=ee

（1）=0l

（1）=le

（2）-6=0d

（1）=0活动a2:

e

（2）=ee

（1）=0l

（2）=le（3）-4=2d

（2）=2活动a3:

e（3）=ee

（1）=0l（3）=le（4）-5=1d（3）=1活动a4:

e（4）=ee

（2）=6l（4）=le（5）-1=6d（4）=0活动a5:

e（5）=ee（3）=4l（5）=le（5）-1=6d（5）=2活动a6:

e（6）=ee（4）=5l（6）=le（6）-2=8d（6）=3活动a7:

e（7）=ee（5）=7l（7）=le（7）-9=7d（7）=0活动a8:

e（8）=ee（5）=7l（8）=le（8）-7=7d（8）=0活动a9:

e（9）=ee（6）=7l（9）=le（8）-4=10d（9）=3活动a10:

e（10）=ee（7）=16l（10）=le（9）-2=16d（10）=0活动a11:

e（11）=ee（8）=14l（11）=le（9）-4=14d（11）=0,e（i）l（i）d（i）,存储结构及算法设计,1、在结点的定义中增加ee和le字段用于记录个事件的最早开始时间和最迟开始时间，同时得到关键路径和最小工期,2、邻接矩阵中使用边权代替原来连接标志1,3、进行拓扑排序，形成拓扑序列,123456789,4、按拓扑序列顺序，从前向后搜索寻找个活动（即边），若存在该活动，则计算相应事件的最早开始时间。

5、按拓扑序列顺序，从后向前搜索寻找个活动（即边），若存在该活动，则计算相应事件的最迟开始时间。

6、计算各活动的最早开始时间和最迟开始时间,本讲小结,图的存储方式一般有两类：

用边的集合表示图和用链接关系表示图。

其中，边的集合方式有邻接矩阵，链接方式有邻接表、十字链表和邻接多重表等。

图结构的接口主要有：

求某结点的各入点/出点，求某结点的各入边/出边、遍历（深度优先和广度优先）。

图比较复杂，还有一些较大的但可以抽象化的操作，如拓扑排序、关键路径、最小生成树、最短路径等。

其中后两种我们安排在最后一章介绍。

事实上，对图的分析，还有许多方面（如网络流量问题、连通性问题、图匹配问题等），这些内容传统地集中在称为网络分析的教程中。

思考与练习,1对p205图，分别写出从结点1出发的深度和广度优先遍历结果。

2编写求图的每个结点的层号的程序。

3针对图的十字链表存储结构，编写深度优先遍历图的程序。

4编写图的邻接表的逆串行化（根据图结构，输出图的边集）程序。

5编写程序，生成图的深度优先树。

6编写程序，生成图的广度优先树。

7改进深度优先遍历程序，使它能同时为每个结点生成对应的深度优先树中的层次号。

8改进深度优先遍历程序，使它能同时求出出发点到其他各点的路径及其长度。