拓扑排序与关键路径

拓扑排序与关键路径第一页，共五十八页，2022年，8月28日有向无环图：一个无环的有向图，简称DAG图。P179图7.22、7.23DAG图：

描述含有公共子式的表达式及工程或系统的进行过程时的有效工具。活动：一个较大的工程被划分成许多子工程，这些子工程被称作活动。活动之间，存在某种约束，如：某些子工程的开始必须在另外一些子工程完成之后。关心问题： 1.工程能否顺利进行 2.估算整个工程完成所必须的最短时间 第二页，共五十八页，2022年，8月28日7.5有向无环图及其应用拓扑排序问题提出：学生选修课程问题顶点——表示课程有向弧——表示先决条件，若课程i是j的先决条件，则图中有弧<i,j>学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业——拓扑排序

定义AOV网——用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(ActivityOnVertexnetwork)，简称AOV网若<vi,vj>是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继AOV网中不允许有回路，这意味着某项活动以自己为先决条件第三页，共五十八页，2022年，8月28日拓扑排序——把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫~检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环拓扑排序的方法在有向图中选一个没有前驱的顶点且输出之从图中删除该顶点和所有以它为尾的弧重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止第四页，共五十八页，2022年，8月28日例课程代号课程名称先修棵C1C2C3C4C5C6C7C8C9C10C11C12无C1C1,C2C1C3,C4C11C3.C5C3,C6无C9C9C1,C9,C10程序设计基础离散数学数据结构汇编语言语言的设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析C1C2C3C4C5C6C7C8C9C10C11C12第五页，共五十八页，2022年，8月28日C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8或：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8一个AOV网的拓扑序列不是唯一的第六页，共五十八页，2022年，8月28日C1C2C3C4C5C6C7C8C9C10C11C12第七页，共五十八页，2022年，8月28日C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1（1）C3C4C5C6C7C8C9C10C11C12拓扑序列：C1--C2（2）第八页，共五十八页，2022年，8月28日C4C5C6C7C8C9C10C11C12拓扑序列：C1--C2--C3（3）C5C6C7C8C9C10C11C12拓扑序列：C1--C2--C3--C4（4）第九页，共五十八页，2022年，8月28日C6C8C10C11C12拓扑序列：C1--C2--C3--C4--C5--C7--C9C6C8C11C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10（8）C6C7C8C9C10C11C12拓扑序列：C1--C2--C3--C4--C5（5）C6C8C9C10C11C12拓扑序列：C1--C2--C3--C4--C5--C7（6）第十页，共五十八页，2022年，8月28日C6C8C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11（9）C8C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6（10）C8拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12（11）拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8（12）第十一页，共五十八页，2022年，8月28日算法实现以邻接表作存储结构设置一个包含n个元素的一维数组indegree，保存AOV网中每个顶点的入度值。把邻接表中所有入度为0的顶点进栈栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1，即indegree[k]-1；若Vk的入度为0则进栈重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕第十二页，共五十八页，2022年，8月28日32104算法描述例1234560122indegree

firstarc

5

5

4

3^^^

adjvex

nextarc3^

2

5^

2

40123456^top16toptop第十三页，共五十八页，2022年，8月28日0122indegree

first

5

5

4

3^^^

adjvex

next3^

2

5^

2

40123456^输出序列：63210416toptop第十四页，共五十八页，2022年，8月28日0122indegree

first

5

5

4

3^^^

adjvex

next3^

2

5^

2

40123456^输出序列：6321041topp第十五页，共五十八页，2022年，8月28日0122indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^输出序列：6321041topp第十六页，共五十八页，2022年，8月28日0122indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^输出序列：6321041topp第十七页，共五十八页，2022年，8月28日0112indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^输出序列：6321041topp第十八页，共五十八页，2022年，8月28日0112indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^输出序列：6321041topp=NULL第十九页，共五十八页，2022年，8月28日0112indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^输出序列：61321041toptop第二十页，共五十八页，2022年，8月28日0112indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^输出序列：6132104topp第二十一页，共五十八页，2022年，8月28日0102indegree

First

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^输出序列：6132104topp4第二十二页，共五十八页，2022年，8月28日0102indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^输出序列：6132104p4top第二十三页，共五十八页，2022年，8月28日0102indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^输出序列：6132104p4top第二十四页，共五十八页，2022年，8月28日0002indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^输出序列：6132104p4top3第二十五页，共五十八页，2022年，8月28日0002indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^输出序列：6132104p4top3第二十六页，共五十八页，2022年，8月28日0002indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^输出序列：6132104p4top3第二十七页，共五十八页，2022年，8月28日0001indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^输出序列：6132104p4top3第二十八页，共五十八页，2022年，8月28日0001indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^输出序列：6132104p=NULL4top3第二十九页，共五十八页，2022年，8月28日0001indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^输出序列：613321044top3第三十页，共五十八页，2022年，8月28日0001indegree

first

5

5

4

3^^^

adjvex

next2^

2

5^

2

40123456^输出序列：613321044topp第三十一页，共五十八页，2022年，8月28日0001indegree

first

5

5

4

3^^^

adjvex

next1^

2

5^

2

40123456^输出序列：613321044topp第三十二页，共五十八页，2022年，8月28日0001indegree

first

5

5

4

3^^^

adjvex

next1^

2

5^

2

40123456^输出序列：613321044topp第三十三页，共五十八页，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next1^

2

5^

2

40123456^输出序列：613321044topp2第三十四页，共五十八页，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next1^

2

5^

2

40123456^输出序列：613321044topp2第三十五页，共五十八页，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next1^

2

5^

2

40123456^输出序列：613321044top2p=NULL第三十六页，共五十八页，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next1^

2

5^

2

40123456^输出序列：6132321044top2p=NULL第三十七页，共五十八页，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next1^

2

5^

2

40123456^输出序列：6132321044topp=NULL第三十八页，共五十八页，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next1^

2

5^

2

40123456^输出序列：61324321044top第三十九页，共五十八页，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next1^

2

5^

2

40123456^输出序列：6132432104topp第四十页，共五十八页，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next0^

2

5^

2

40123456^输出序列：6132432104topp5第四十一页，共五十八页，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next0^

2

5^

2

40123456^输出序列：6132432104topp=NULL5第四十二页，共五十八页，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next0^

2

5^

2

40123456^输出序列：61324532104top5第四十三页，共五十八页，2022年，8月28日0000indegree

first

5

5

4

3^^^

adjvex

next0^

2

5^

2

40123456^输出序列：61324532104topp=NULL第四十四页，共五十八页，2022年，8月28日算法分析--算法7.12建邻接表：T(n)=O(e)搜索入度为0的顶点的时间：T(n)=O(n)拓扑排序：T(n)=O(n+e)第四十五页，共五十八页，2022年，8月28日关键路径问题提出把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始例设一个工程有11项活动，9个事件事件V1——表示整个工程开始事件V9——表示整个工程结束问题：（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4第四十六页，共五十八页，2022年，8月28日定义AOE网(ActivityOnEdge)——也叫边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间路径长度——路径上各活动持续时间之和关键路径——路径长度最长的路径叫~Ve(j)——表示事件Vj的最早发生时间Vl(j)——表示事件Vj的最迟发生时间e(i)——表示活动ai的最早开始时间l(i)——表示活动ai的最迟开始时间l(i)-e(i)——表示完成活动ai的时间余量关键活动——关键路径上的活动叫~，即l(i)=e(i)的活动第四十七页，共五十八页，2022年，8月28日问题分析如何找e(i)=l(i)的关键活动？设活动ai用弧<j,k>表示，其持续时间记为：dut(<j,k>)则有：（1）e(i)=Ve(j)

（2）l(i)=Vl(k)-dut(<j,k>)jkai如何求Ve(j)和Vl(j)？(1)从Ve(1)=0开始递推(2)从Vl(n)=Ve(n)开始递推第四十八页，共五十八页，2022年，8月28日求关键路径步骤求Ve(i)求Vl(j)求e(i)求l(i)计算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9顶点VeVl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动ell-e00002266046258377077071031616014140033第四十九页，共五十八页，2022年，8月28日算法实现以邻接表作存储结构从源点V1出发，令Ve[1]=0,按拓扑序列求各顶点的Ve[i]从汇点Vn出发，令Vl[n]=Ve[n],按逆拓扑序列求其余各顶点的Vl[i]根据各顶点的Ve和Vl值，计算每条弧的e[i]和l[i],找出e[i]=l[i]的关键活动第五十页，共五十八页，2022年，8月28日算法描述1-输入顶点和弧信息，建立其邻接表计算每个顶点的入度2-对其进行拓扑排序2.1-排序过程中求顶点的Ve[i]2.2-将得到的拓扑序列进栈3-按逆拓扑序列求顶点的Vl[i]4-计算每条弧的e[i]和l[i],找出e[i]=l[i]的关键活动第五十一页，共五十八页，2022年，8月28日StatusTopologicalOrder(ALGraphG,Stack&T){//算法7.13//有向网G采用邻接表存储结构，求各顶点事件的最早发生时间ve(全局变量)。

//T为拓扑序列定点栈，S为零入度顶点栈。

//若G无回路，则用栈T返回G的一个拓扑序列，且函数值为OK，否则为ERROR。

StackS;intcount=0,k;charindegree[40];ArcNode*p;InitStack(S);FindInDegree(G,indegree);//对各顶点求入度indegree[0..vernum-1]for(intj=0;j<G.vexnum;++j)//建零入度顶点栈Sif(indegree[j]==0)Push(S,j);//入度为0者进栈

InitStack(T);//建拓扑序列顶点栈Tcount=0;for(inti=0;i<G.vexnum;i++)ve[i]=0;//初始化

while(!StackEmpty(S)){Pop(S,j);Push(T,j);++count;//j号顶点入T栈并计数

for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;//对j号顶点的每个邻接点的入度减1if(--indegree[k]==0)Push(S,k);//若入度减为0，则入栈

if(ve[j]+p->info>ve[k])ve[k]=ve[j]+p->info;}//for*(p->info)=dut(<j,k>)}//whileif(count<G.vexnum)returnERROR;//该有向网有回路

elsereturnOK;}//TopologicalOrder第五十二页，共五十八页，2022年，8月28日StatusCriticalPath(ALGraphG){//算法7.14,G为有向网，输出G的各项关键活动。StackT;inta,j,k,el,ee,dut;chartag;ArcNode*p;if(!TopologicalOrder(G,T))returnERROR;for(a=0;a<G.vexnum;a++)