拓扑排序与关键路径课件

v有向无环图有向无环图：一个无环的有向图，简称一个无环的有向图，简称DAG图。图。P179 图图7.22、7.23DAG图：图：描述含有公共子式的表达式及工程或系统的进行过程时的有描述含有公共子式的表达式及工程或系统的进行过程时的有效工具。效工具。v活动活动：一个较大的工程被划分成许多子工程，这些子工程被：一个较大的工程被划分成许多子工程，这些子工程被称作活动。活动之间，存在某种约束，如：某些子工程的开称作活动。活动之间，存在某种约束，如：某些子工程的开始必须在另外一些子工程完成之后。始必须在另外一些子工程完成之后。v关心问题：关心问题：1.工程能否顺利进行工程能否顺利进行2.估算估算 整个工程完成所必须的最短时间整个工程完成所必须的最短时间有向无环图：1v7.5有向无环图及其应用有向无环图及其应用v拓扑排序拓扑排序问题提出：学生选修课程问题问题提出：学生选修课程问题顶点顶点表示课程表示课程有向弧有向弧表示先决条件，若课程表示先决条件，若课程i是是j的先决条件，则图中有弧的先决条件，则图中有弧学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业拓扑排序拓扑排序定义定义vAOV网网用顶点表示活动，用弧表示活动间优先关系的有向图称用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网为顶点表示活动的网(Activity On Vertex network)，简称，简称AOV网网若若是图中有向边，则是图中有向边，则vi是是vj的的直接前驱直接前驱；vj是是vi的的直接后直接后继继AOV网中不允许有回路，这意味着某项活动以自己为先决条件网中不允许有回路，这意味着某项活动以自己为先决条件7.5有向无环图及其应用2v拓扑排序拓扑排序把把AOV网络中各顶点按照它们相互网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫之间的优先关系排列成一个线性序列的过程叫检测检测AOV网中是否存在环方法：网中是否存在环方法：对有向图构造对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该的拓扑有序序列中，则该AOV网必定不存在环网必定不存在环拓扑排序的方法拓扑排序的方法v在有向图中选一个没有前驱的顶点且输出之在有向图中选一个没有前驱的顶点且输出之v从图中删除该顶点和所有以它为尾的弧从图中删除该顶点和所有以它为尾的弧v重复上述两步，直至全部顶点均已输出；或者当重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止图中不存在无前驱的顶点为止拓扑排序把AOV网络中各顶点按照它们相互之间的优先关系排3例例课程代号课程代号 课程名称课程名称 先修棵先修棵C1C2C3C4C5C6C7C8C9C10C11C12无无C1C1,C2C1C3,C4C11C3.C5C3,C6无无C9C9C1,C9,C10程序设计基础程序设计基础离散数学离散数学数据结构数据结构汇编语言汇编语言语言的设计和分析语言的设计和分析计算机原理计算机原理编译原理编译原理操作系统操作系统高等数学高等数学线性代数线性代数普通物理普通物理数值分析数值分析C1C2C3C4C5C6C7C8C9C10C11C12例课程代号 课程名称 4C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：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网的拓扑序列不是唯一的网的拓扑序列不是唯一的C1C2C3C4C5C6C7C8C9C10C11C12拓扑序5C1C2C3C4C5C6C7C8C9C10C11C12C1C2C3C4C5C6C7C8C9C10C11C126C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1（1）C3C4C5C6C7C8C9C10C11C12拓扑序列：C1-C2（2）C2C3C4C5C6C7C8C9C10C11C12拓扑序列：7C4C5C6C7C8C9C10C11C12拓扑序列：C1-C2-C3（3）C5C6C7C8C9C10C11C12拓扑序列：C1-C2-C3-C4（4）C4C5C6C7C8C9C10C11C12拓扑序列：C1-8C6C8C10C11C12拓扑序列：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）C6C8C10C11C12拓扑序列：C1-C2-C3-9C6C8C12拓扑序列：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）C6C8C12拓扑序列：C1-C2-C3-C4-C510算法实现以邻接表作存储结构设置一个包含n个元素的一维数组indegree，保存AOV网中每个顶点的入度值。把邻接表中所有入度为0的顶点进栈栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1，即indegreek-1；若Vk的入度为0则进栈重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕算法实现1132104算法描述例1234560122indegree firstarc 5 5 4 3 adjvex nextarc3 2 5 2 40123456top16toptop32104算法描述例1234560122indegree 120122indegree first 5 5 4 3 adjvex next3 2 5 2 40123456输出序列：63210416toptop0122indegree first 5 5 4 3130122indegree first 5 5 4 3 adjvex next3 2 5 2 40123456输出序列：6321041topp0122indegree first 5 5 4 3140122indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6321041topp0122indegree first 5 5 4 3150122indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6321041topp0122indegree first 5 5 4 3160112indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6321041topp0112indegree first 5 5 4 3170112indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6321041topp=NULL0112indegree first 5 5 4 3180112indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 1321041toptop0112indegree first 5 5 4 3190112indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 132104topp0112indegree first 5 5 4 3200102indegree First 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 132104topp40102indegree First 5 5 4 3210102indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 132104p4top0102indegree first 5 5 4 3220102indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 132104p4top0102indegree first 5 5 4 3230002indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 132104p4top30002indegree first 5 5 4 3240002indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 132104p4top30002indegree first 5 5 4 3250002indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 132104p4top30002indegree first 5 5 4 3260001indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 132104p4top30001indegree first 5 5 4 3270001indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 132104p=NULL4top30001indegree first 5 5 4 3280001indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 1 3321044top30001indegree first 5 5 4 3290001indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 1 3321044topp0001indegree first 5 5 4 300001indegree first 5 5 4 3 adjvex next1 2 5 2 40123456输出序列：6 1 3321044topp0001indegree first 5 5 4310001indegree first 5 5 4 3 adjvex next1 2 5 2 40123456输出序列：6 1 3321044topp0001indegree first 5 5 4 3320000indegree first 5 5 4 3 adjvex next1 2 5 2 40123456输出序列：6 1 3321044topp20000indegree first 5 5 4 3330000indegree first 5 5 4 3 adjvex next1 2 5 2 40123456输出序列：6 1 3321044topp20000indegree first 5 5 4 340000indegree first 5 5 4 3 adjvex next1 2 5 2 40123456输出序列：6 1 3321044top2p=NULL0000indegree first 5 5 4 350000indegree first 5 5 4 3 adjvex next1 2 5 2 40123456输出序列：6 1 3 2321044top2p=NULL0000indegree first 5 5 4 360000indegree first 5 5 4 3 adjvex next1 2 5 2 40123456输出序列：6 1 3 2321044topp=NULL0000indegree first 5 5 4 370000indegree first 5 5 4 3 adjvex next1 2 5 2 40123456输出序列：6 1 3 2 4321044top0000indegree first 5 5 4 3380000indegree first 5 5 4 3 adjvex next1 2 5 2 40123456输出序列：6 1 3 2 432104topp0000indegree first 5 5 4390000indegree first 5 5 4 3 adjvex next0 2 5 2 40123456输出序列：6 1 3 2 432104topp50000indegree first 5 5 4 400000indegree first 5 5 4 3 adjvex next0 2 5 2 40123456输出序列：6 1 3 2 432104topp=NULL50000indegree first 5 5 4 410000indegree first 5 5 4 3 adjvex next0 2 5 2 40123456输出序列：6 1 3 2 4 532104top50000indegree first 5 5 4 3420000indegree first 5 5 4 3 adjvex next0 2 5 2 40123456输出序列：6 1 3 2 4 532104topp=NULL0000indegree first 5 5 4 43算法分析-算法7.12建邻接表：T(n)=O(e)搜索入度为0的顶点的时间：T(n)=O(n)拓扑排序：T(n)=O(n+e)算法分析-算法7.12建邻接表：T(n)=O(e)44v关键路径问题提出把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始例 设一个工程有11项活动，9个事件事件 V1表示整个工程开始事件V9表示整个工程结束问题：（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4关键路径把工程计划表示为有向图，用顶点表示事件，弧表示活动；45定义vAOE网(Activity On Edge)也叫边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间v路径长度路径上各活动持续时间之和v关键路径路径长度最长的路径叫vVe(j)表示事件Vj的最早发生时间vVl(j)表示事件Vj的最迟发生时间ve(i)表示活动ai的最早开始时间vl(i)表示活动ai的最迟开始时间vl(i)-e(i)表示完成活动ai的时间余量v关键活动关键路径上的活动叫，即l(i)=e(i)的活动定义46问题分析v如何找e(i)=l(i)的关键活动？设活动ai用弧表示，其持续时间记为：dut()则有：（1）e(i)=Ve(j)（2）l(i)=Vl(k)-dut()jkai如何求Ve(j)和Vl(j)？(1)从从Ve(1)=0开始递推开始递推(2)从从Vl(n)=Ve(n)开始递推开始递推问题分析设活动ai用弧表示，其持续时间记为：dut47求关键路径步骤v求Ve(i)v求Vl(j)v求e(i)v求l(i)v计算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9顶点 Ve Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动 e l l-e00002266046258377077071031616014140033求关键路径步骤987645321a2=4a3=5a5=1a648算法实现以邻接表作存储结构从源点V1出发，令Ve1=0,按拓扑序列求各顶点的Vei从汇点Vn出发，令Vln=Ven,按逆拓扑序列求其余各顶点的Vli根据各顶点的Ve和Vl值，计算每条弧的ei和li,找出ei=li的关键活动算法实现49算法描述1-输入顶点和弧信息，建立其邻接表 计算每个顶点的入度2-对其进行拓扑排序2.1-排序过程中求顶点的Vei2.2-将得到的拓扑序列进栈3-按逆拓扑序列求顶点的Vli4-计算每条弧的ei和li,找出ei=li的关键活动算法描述50Status TopologicalOrder(ALGraph G,Stack&T)/算法算法7.13 /有向网有向网G采用邻接表存储结构，求各顶点事件的最早发生时间采用邻接表存储结构，求各顶点事件的最早发生时间ve(全局变量全局变量)。/T为拓扑序列定点栈，为拓扑序列定点栈，S为零入度顶点栈。为零入度顶点栈。/若若G无回路，则用栈无回路，则用栈T返回返回G的一个拓扑序列，且函数值为的一个拓扑序列，且函数值为OK，否则为，否则为ERROR。Stack S;int count=0,k;char indegree40;ArcNode*p;InitStack(S);FindInDegree(G,indegree);/对各顶点求入度对各顶点求入度indegree0.vernum-1 for(int j=0;jG.vexnum;+j)/建零入度顶点栈建零入度顶点栈S if(indegreej=0)Push(S,j);/入度为入度为0者进栈者进栈 InitStack(T);/建拓扑序列顶点栈建拓扑序列顶点栈T count=0;for(int i=0;inextarc)k=p-adjvex;/对对j号顶点的每个邻接点的入度减号顶点的每个邻接点的入度减1 if(-indegreek=0)Push(S,k);/若入度减为若入度减为0，则入栈，则入栈 if(vej+p-info vek)vek=vej+p-info;/for *(p-info)=dut()/while if(countG.vexnum)return ERROR;/该有向网有回路该有向网有回路 else return OK;/TopologicalOrderStatus TopologicalOrder(ALGrap51Status CriticalPath(ALGraph G)/算法算法7.14,G为有向网，输出为有向网，输出G的各项关键活动。的各项关键活动。Stack T;int a,j,k,el,ee,dut;char tag;ArcNode*p;if(!TopologicalOrder(G,T)return ERROR;for(a=0;anextarc)k=p-adjvex;dut=p-info;/dut if(vlk-dut vlj)vlj=vlk-dut;/for(j=0;jnextarc)k=p-adjvex;dut=p-info;ee=vej;el=vlk-dut;tag=(ee=el)?*:;printf(j,k,dut,ee,el,tag);/输出关键活动输出关键活动 return OK;/CriticalPathStatus CriticalPath(ALGraph G)52拓扑排序与关键路径课件53987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4inlinkvexnextvexdatalength123456789123456789011121122 26 34 45 79 51 62 51 87 84 910 94987645321a2=4a3=5a5=1a6=2a9=4a54对图示的对图示的AOE 网络，计算各活动弧的网络，计算各活动弧的e(ai)和和l(ai)的函数的函数值，各事件（顶点）的值，各事件（顶点）的ve（Vj）和）和vl(Vj)的函数值，列的函数值，列出各条关键路径。出各条关键路径。对图示的AOE 网络，计算各活动弧的e(ai)和l(ai)的55拓扑排序与关键路径课件56拓扑排序与关键路径课件57