数据结构.第7章.图.3.有向无环图及其应用

武汉科技大学WuhanUniversityofScienceandTechnology张凯计算机学院软件工程系2011年3月12日图的连通性问题第7章图图的定义和术语图的存储结构图的遍历有向无环图及其应用最短路径有向无环图§7.5有向无环图及其应用有向无环图(Directedacyclinegraph)简称DAG图，是描述一项工程或系统的进行过程的有效工具。v1v2v3v1v2v3有向无环图有向图有向无环图§7.5有向无环图及其应用对整个工程和系统，人们关心的是两个方面的问题：一是工程能否顺利进行；二是估算整个工程完成所必须的最短时间。有向无环图的应用：拓扑排序关键路径有向无环图§7.5有向无环图及其应用在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：①先后关系，即必须在一子项目完成后，才能开始实施另一个子项目；②子项目之间无次序要求，即两个子项目可以同时进行，互不影响。两种常用的活动网络(ActivityNetwork)§7.5有向无环图及其应用②AOE网(ActivityOnEdges)—用边表示活动的网络AOE网定义：如果在无环的带权有向图中，用有向边表示一个工程中的活动，用边上权值表示活动持续时间，用顶点表示事件，则这样的有向图叫做用边表示活动的网络，简称AOE。①AOV网(ActivityOnVertices)—用顶点表示活动的网络AOV网定义：若用有向图表示一个工程，在图中用顶点表示活动，用弧表示活动间的优先关系。vi必须先于活动vj进行。则这样的有向图叫做用顶点表示活动的网络，简称AOV。AOV网络§7.5有向无环图及其应用用途：我们经常用有向图来描述一个工程或系统的进行过程。一般来说，一个工程可以分为若干个子工程，只要完成了这些子工程，就可以导致整个工程的完成。例：AOV网络若用于教学计划的制定，可以解决：哪些课程是必须先修的，哪些课程是可以并行学习的。AOV网络§7.5有向无环图及其应用课程编号课程名称先导课程编号C1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5算法分析与设计C3，C4C6计算机组成原理C11C7编译原理C5，C3C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9，C10，C1AOV网络§7.5有向无环图及其应用C1C4C2C3C5C9C7C12C10C11C6C8AOV网络§7.5有向无环图及其应用C1C4C2C3C5C9C7C12C10C11C6C8课程编号课程名称先导课程编号C1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5算法分析与设计C3，C4C6计算机组成原理C11C7编译原理C5，C3C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9，C10，C1C1C2C3C4C5C7C9C10C11C6C12C8§7.5有向无环图及其应用C1C9C4C2C12C10C11C3C5C6C7C8C1拓扑序列：C2C3C4C5C7C9C10C11C6C12C8拓扑排序§7.5有向无环图及其应用对一个有向无环图中的顶点排成一个具有前后次序的线性序列。拓扑排序算法：重复选择没有直接前驱的顶点。拓扑排序§7.5有向无环图及其应用1.输入AOV网络。令n为顶点个数。2.在AOV网络中选一个没有直接前驱的顶点,并输出之;3.从图中删去该顶点,同时删去所有它发出的有向边;4.重复以上2、3步,直到：全部顶点均已输出，拓扑有序序列形成，拓扑排序完成或者，图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。拓扑排序§7.5有向无环图及其应用V1V2V4V3V6V5例：§7.5有向无环图及其应用G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^另外增设一个存放各顶点的入度值的一维数组IndegreeV1V2V4V3V6V5021354indegree[0..5]021230012345§7.5有向无环图及其应用G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^indegree[0..5]02123001234550sV1V2V4V3V6V5021354§7.5有向无环图及其应用G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^indegree[0..5]0212300123450s5打印G.vertices[5].data4号和3号顶点的入度分别减1V1V2V4V3V6V5021354§7.5有向无环图及其应用G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^indegree[0..5]0211200123450sV1V2V4V3V6V5021354§7.5有向无环图及其应用G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^indegree[0..5]021120012345s0打印G.vertices[0].data3号、2号、1号顶点的入度分别减1V1V2V4V3V6V5021354§7.5有向无环图及其应用G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^indegree[0..5]01002001234523sV1V2V4V3V6V5021354§7.5有向无环图及其应用G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^indegree[0..5]01002001234523sV1V2V4V3V6V5021354§7.5有向无环图及其应用G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^indegree[0..5]0100200123453s2打印G.vertices[2].data4号、1号顶点的入度分别减1V1V2V4V3V6V5021354§7.5有向无环图及其应用G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^indegree[0..5]00001001234513sV1V2V4V3V6V5021354§7.5有向无环图及其应用G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^indegree[0..5]0000100123453s1打印G.vertices[1].dataV1V2V4V3V6V5021354§7.5有向无环图及其应用G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^indegree[0..5]0000100123453sV1V2V4V3V6V5021354§7.5有向无环图及其应用G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^indegree[0..5]000010012345s3打印G.vertices[3].data4号顶点的入度减1V1V2V4V3V6V5021354§7.5有向无环图及其应用G.vertices[0]v1321^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^indegree[0..5]0000000123454sV1V2V4V3V6V5021354§7.5有向无环图及其应用G.vertices[0]v131^G.vertices[1]v2^G.vertices[2]v341^G.vertices[3]v44^G.vertices[4]v5^G.vertices[5]v643^indegree[0..5]000000012345s4打印G.vertices[4].data最后输出的拓扑序列为：v6v1v3v2v4v5V1V2V4V3V6V50213542§7.5有向无环图及其应用StatusTopologicalSort(ALGraphG){//采用邻接表存储结构。若G无回路，则输出拓扑序列并返回OK，否则ERRORFindInDegree(G，indegree)；//对各顶点求入度indegree[0..vernum-1]InitStack(S)；//建零入度顶点栈for(i=0；iG.vexnum；++i)if(!indegree[i])Push(S，i)//入度为0者进栈count=0；//对输出顶点计数while(!StackEmpty(S)){Pop(S，i);printf(i，G.vertices[i].data);++count;//输出i号顶点并计数for(p=G.vertices[i].firstarc;p;p=p-nextarc){k=p—adivex；//对i号顶点的每个邻接点入度减1if(！(--indegree[k]))Push(S，k);//若入度减为0，则入栈}//for}//whileif(countG.vexnum)returnERROR;//该有向图有回路elsereturnOK；}//TopologicalSort关键路径§7.5有向无环图及其应用对整个工程和系统，人们关心的是两个方面的问题(1)工程能否顺利进行对AOV网进行拓扑排序(2)估算整个工程完成所必须的最短时间对AOE网求关键路径AOE网§7.5有向无环图及其应用AOE－网(ActivityOnEdgeNetwork)：即边表示活动的网。AOE网是一个带权的有向无环图。其中：顶点表示事件(Event)，弧表示活动(Activity)，权值表示活动持续的时间。通常可用AOE网来估算工程的完成时间。AOE网§7.5有向无环图及其应用v9表示整个工程的结束v5表示a4和a5已经完成，a7和a8可以开始与每个活动相联系的数是执行该活动所需的时间v1表示整个工程的开始v1v2v3v4v5v6v7v8v9a6=2AOE网§7.5有向无环图及其应用上图AOE网中：共有1