数据结构拓扑排序关键路径精品文稿.ppt
数据结构拓扑排序关键路径第1页，本讲稿共58页v有向无环图有向无环图：一个无环的有向图，简称一个无环的有向图，简称DAG图。图。P179 图图7.22、7.23DAG图：图：描述含有公共子式的表达式及工程或系统的进行过程时的有效描述含有公共子式的表达式及工程或系统的进行过程时的有效工具。工具。v活动活动：一个较大的工程被划分成许多子工程，这些子工程被称作活动。：一个较大的工程被划分成许多子工程，这些子工程被称作活动。活动之间，存在某种约束，如：某些子工程的开始必须在另外一些子工活动之间，存在某种约束，如：某些子工程的开始必须在另外一些子工程完成之后。程完成之后。v关心问题：关心问题：1.工程能否顺利进行工程能否顺利进行2.估算估算 整个工程完成所必须的最短时间整个工程完成所必须的最短时间第2页，本讲稿共58页v7.5有向无环图及其应用有向无环图及其应用v拓扑排序拓扑排序问题提出：学生选修课程问题问题提出：学生选修课程问题顶点顶点表示课程表示课程有向弧有向弧表示先决条件，若课程表示先决条件，若课程i是是j的先决条件，则图中有弧的先决条件，则图中有弧学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业拓扑拓扑排序排序定义定义vAOV网网用顶点表示活动，用弧表示活动间优先关系的有向图称为顶用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网点表示活动的网(Activity On Vertex network)，简称，简称AOV网网若若是图中有向边，则是图中有向边，则vi是是vj的的直接前驱直接前驱；vj是是vi的的直接后直接后继继AOV网中不允许有回路，这意味着某项活动以自己为先决条件网中不允许有回路，这意味着某项活动以自己为先决条件第3页，本讲稿共58页v拓扑排序拓扑排序把把AOV网络中各顶点按照它们相互之间网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫的优先关系排列成一个线性序列的过程叫检测检测AOV网中是否存在环方法：网中是否存在环方法：对有向图构造其顶对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该序列中，则该AOV网必定不存在环网必定不存在环拓扑排序的方法拓扑排序的方法v在有向图中选一个没有前驱的顶点且输出之在有向图中选一个没有前驱的顶点且输出之v从图中删除该顶点和所有以它为尾的弧从图中删除该顶点和所有以它为尾的弧v重复上述两步，直至全部顶点均已输出；或者当图中不重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止存在无前驱的顶点为止第4页，本讲稿共58页例例课程代号课程代号 课程名称课程名称 先修棵先修棵C1C2C3C4C5C6C7C8C9C10C11C12无无C1C1,C2C1C3,C4C11C3.C5C3,C6无无C9C9C1,C9,C10程序设计基础程序设计基础离散数学离散数学数据结构数据结构汇编语言汇编语言语言的设计和分析语言的设计和分析计算机原理计算机原理编译原理编译原理操作系统操作系统高等数学高等数学线性代数线性代数普通物理普通物理数值分析数值分析C1C2C3C4C5C6C7C8C9C10C11C12第5页，本讲稿共58页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网的拓扑序列不是唯一的网的拓扑序列不是唯一的第6页，本讲稿共58页C1C2C3C4C5C6C7C8C9C10C11C12第7页，本讲稿共58页C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1（1）C3C4C5C6C7C8C9C10C11C12拓扑序列：C1-C2（2）第8页，本讲稿共58页C4C5C6C7C8C9C10C11C12拓扑序列：C1-C2-C3（3）C5C6C7C8C9C10C11C12拓扑序列：C1-C2-C3-C4（4）第9页，本讲稿共58页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）第10页，本讲稿共58页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）第11页，本讲稿共58页算法实现以邻接表作存储结构设置一个包含n个元素的一维数组indegree，保存AOV网中每个顶点的入度值。把邻接表中所有入度为0的顶点进栈栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1，即indegreek-1；若Vk的入度为0则进栈重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕第12页，本讲稿共58页32104算法描述例1234560122indegree firstarc 5 5 4 3 adjvex nextarc3 2 5 2 40123456top16toptop第13页，本讲稿共58页0122indegree first 5 5 4 3 adjvex next3 2 5 2 40123456输出序列：63210416toptop第14页，本讲稿共58页0122indegree first 5 5 4 3 adjvex next3 2 5 2 40123456输出序列：6321041topp第15页，本讲稿共58页0122indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6321041topp第16页，本讲稿共58页0122indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6321041topp第17页，本讲稿共58页0112indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6321041topp第18页，本讲稿共58页0112indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6321041topp=NULL第19页，本讲稿共58页0112indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 1321041toptop第20页，本讲稿共58页0112indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 132104topp第21页，本讲稿共58页0102indegree First 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 132104topp4第22页，本讲稿共58页0102indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 132104p4top第23页，本讲稿共58页0102indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 132104p4top第24页，本讲稿共58页0002indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 132104p4top3第25页，本讲稿共58页0002indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 132104p4top3第26页，本讲稿共58页0002indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 132104p4top3第27页，本讲稿共58页0001indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 132104p4top3第28页，本讲稿共58页0001indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 132104p=NULL4top3第29页，本讲稿共58页0001indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 1 3321044top3第30页，本讲稿共58页0001indegree first 5 5 4 3 adjvex next2 2 5 2 40123456输出序列：6 1 3321044topp第31页，本讲稿共58页0001indegree first 5 5 4 3 adjvex next1 2 5 2 40123456输出序列：6 1 3321044topp第32页，本讲稿共58页0001indegree first 5 5 4 3 adjvex next1 2 5 2 40123456输出序列：6 1 3321044topp第33页，本讲稿共58页0000indegree first 5 5 4 3 adjvex next1 2 5 2 40123456输出序列：6 1 3321044topp2第34页，本讲稿共58页0000indegree first 5 5 4 3 adjvex next1 2 5 2 40123456输出序列：6 1 3321044topp2第35页，本讲稿共58页0000indegree first 5 5 4 3 adjvex next1 2 5 2 40123456输出序列：6 1 3321044top2p=NULL第36页，本讲稿共58页0000indegree first 5 5 4 3 adjvex next1 2 5 2 40123456输出序列：6 1 3 2321044top2p=NULL第37页，本讲稿共58页0000indegree first 5 5 4 3 adjvex next1 2 5 2 40123456输出序列：6 1 3 2321044topp=NULL第38页，本讲稿共58页0000indegree first 5 5 4 3 adjvex next1 2 5 2 40123456输出序列：6 1 3 2 4321044top第39页，本讲稿共58页0000indegree first 5 5 4 3 adjvex next1 2 5 2 40123456输出序列：6 1 3 2 432104topp第40页，本讲稿共58页0000indegree first 5 5 4 3 adjvex next0 2 5 2 40123456输出序列：6 1 3 2 432104topp5第41页，本讲稿共58页0000indegree first 5 5 4 3 adjvex next0 2 5 2 40123456输出序列：6 1 3 2 432104topp=NULL5第42页，本讲稿共58页0000indegree first 5 5 4 3 adjvex next0 2 5 2 40123456输出序列：6 1 3 2 4 532104top5第43页，本讲稿共58页0000indegree first 5 5 4 3 adjvex next0 2 5 2 40123456输出序列：6 1 3 2 4 532104topp=NULL第44页，本讲稿共58页算法分析-算法7.12建邻接表：T(n)=O(e)搜索入度为0的顶点的时间：T(n)=O(n)拓扑排序：T(n)=O(n+e)第45页，本讲稿共58页v关键路径问题提出把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始例 设一个工程有11项活动，9个事件事件 V1表示整个工程开始事件V9表示整个工程结束问题：（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4第46页，本讲稿共58页定义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)的活动第47页，本讲稿共58页问题分析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)开始递推开始递推第48页，本讲稿共58页求关键路径步骤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第49页，本讲稿共58页算法实现以邻接表作存储结构从源点V1出发，令Ve1=0,按拓扑序列求各顶点的Vei从汇点Vn出发，令Vln=Ven,按逆拓扑序列求其余各顶点的Vli根据各顶点的Ve和Vl值，计算每条弧的ei和li,找出ei=li的关键活动第50页，本讲稿共58页算法描述1-输入顶点和弧信息，建立其邻接表 计算每个顶点的入度2-对其进行拓扑排序2.1-排序过程中求顶点的Vei2.2-将得到的拓扑序列进栈3-按逆拓扑序列求顶点的Vli4-计算每条弧的ei和li,找出ei=li的关键活动第51页，本讲稿共58页Status 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;/TopologicalOrder第52页，本讲稿共58页Status 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;/CriticalPath第53页，本讲稿共58页第54页，本讲稿共58页987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4inlinkvexnextvexdatalength123456789123456789011121122 26 34 45 79 51 62 51 87 84 910 94第55页，本讲稿共58页对图示的对图示的AOE 网络，计算各活动弧的网络，计算各活动弧的e(ai)和和l(ai)的函数值，的函数值，各事件（顶点）的各事件（顶点）的ve（Vj）和）和vl(Vj)的函数值，列出各条关的函数值，列出各条关键路径。键路径。第56页，本讲稿共58页第57页，本讲稿共58页第58页，本讲稿共58页
