《aov网和拓扑排序.ppt》由会员分享，可在线阅读，更多相关《aov网和拓扑排序.ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 7.5 7.5 7.5 7.5 有向无环图及应用有向无环图及应用有向无环图及应用有向无环图及应用一一一一 AOV-AOV-网网网网二二二二 AOV-AOV-网与拓扑排序网与拓扑排序网与拓扑排序网与拓扑排序三三三三 AOE-AOE-网与关键路径网与关键路径网与关键路径网与关键路径有向无环图有向无环图 及应用及应用u有向无环图的定义有向无环图的定义u有向图中是否有环的检查有向图中是否有环的检查u有向无环图的应用有向无环图的应用:u 工程能否顺利进行工程能否顺利进行拓扑排序拓扑排序u 估算完成工程的最短时间估算完成工程的最短时间关键路径关键路径有向无环图有向无环图有向无环图有向无环图有向无环图（有
2、向无环图（有向无环图（有向无环图（DAGDAG图）：图）：图）：图）：没有回路没有回路没有回路没有回路(环环环环)的有向图。的有向图。的有向图。的有向图。有向无环图有向无环图有向无环图有向无环图有向图（有环）有向图（有环）有向图（有环）有向图（有环）一、一、一、一、AOV-AOV-AOV-AOV-网网网网(Activity On Vertices)Activity On Vertices)表示工程的有向图中，用表示工程的有向图中，用顶点表示活动顶点表示活动，用，用有向边有向边表示活动表示活动Vi 必须先于活动必须先于活动Vj 进行进行。这种有向图叫做顶点表示活动的。这种有向图叫做顶点表示活动的
3、AOV网络网络。（用顶点表示活动，弧表示活动间的优先关系的有向图）用顶点表示活动，弧表示活动间的优先关系的有向图）在在AOV网络中不能出现有向回路（即有向环）。网络中不能出现有向回路（即有向环）。若出现了有向环，则意味着某项活动应以自己作为先决条件。因此，对给定的若出现了有向环，则意味着某项活动应以自己作为先决条件。因此，对给定的AOV网络，必须先判断它是否存在有向环。网络，必须先判断它是否存在有向环。检查有向图中是否存在回路的方法之一，是对有向图进行检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序拓扑排序.。何谓何谓“拓扑排序拓扑排序”？对有向图进行如下操作:按照有向图给出的次序关
4、系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为由此所得顶点的线性序列称之为拓扑有序序列拓扑有序序列.拓扑排序拓扑排序是对有向无环图的顶点的一种排序是对有向无环图的顶点的一种排序。拓扑排序拓扑排序 举例举例 课程编号课程编号 课程名称课程名称 先修课程先修课程 C1 高等数学高等数学 无无 C2 程序设计基础程序设计基础 无无 C3 离散数学离散数学 C1,C2 C4 数据结构数据结构 C3,C2 C5 高级语言程序设计高级语言程序设计 C2 C6 编译方法编译方法 C5,C4 C7 操作系统操作系统 C4,C9 C
5、8 普通物理普通物理 C1 C9 计算机原理计算机原理 C8表示教学计划（课程之间）的优先关系有向图表示教学计划（课程之间）的优先关系有向图C8C3C5C4C9C6C7C1C2n对图进行拓扑排序对图进行拓扑排序,得到的拓扑有序序列为得到的拓扑有序序列为 C1,C2,C3,C4,C5,C6,C8,C9,C7或或 C1,C8,C9,C2,C5,C3,C4,C7,C6n构造拓扑有序序列构造拓扑有序序列，即将各个顶点，即将各个顶点(代表各个活动代表各个活动)排列成一个线性排列成一个线性有序的序列，使得有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到网络中所有应存在的前驱和后继关系都能得到
6、满足。满足。n构造构造AOV网络全部顶点的拓扑有序序列的运算称为拓扑排序。网络全部顶点的拓扑有序序列的运算称为拓扑排序。n如果通过拓扑排序能将如果通过拓扑排序能将如果通过拓扑排序能将如果通过拓扑排序能将AOVAOV网络的所有顶点都排入一个拓扑有序网络的所有顶点都排入一个拓扑有序网络的所有顶点都排入一个拓扑有序网络的所有顶点都排入一个拓扑有序 的序列中的序列中的序列中的序列中,则该网络中必定不会出现有向环。则该网络中必定不会出现有向环。则该网络中必定不会出现有向环。则该网络中必定不会出现有向环。n如果如果如果如果AOVAOV网络中存在有向环，此网络中存在有向环，此网络中存在有向环，此网络中存在有
7、向环，此AOVAOV网络所代表的工程是不可行的。网络所代表的工程是不可行的。网络所代表的工程是不可行的。网络所代表的工程是不可行的。拓扑排序方法拓扑排序方法拓扑排序方法拓扑排序方法 重复以上重复以上重复以上重复以上 、步步步步,直到直到直到直到F 全部顶点均已输出，全部顶点均已输出，全部顶点均已输出，全部顶点均已输出，拓扑有序序列形成，拓扑排序完拓扑有序序列形成，拓扑排序完拓扑有序序列形成，拓扑排序完拓扑有序序列形成，拓扑排序完成；或成；或成；或成；或F 图中还有未输出的顶点图中还有未输出的顶点图中还有未输出的顶点图中还有未输出的顶点,但已跳出处理循环。但已跳出处理循环。但已跳出处理循环。但已
8、跳出处理循环。说明图说明图说明图说明图中还剩下一些顶点中还剩下一些顶点中还剩下一些顶点中还剩下一些顶点,它们都有直接前驱。这时网络中必存它们都有直接前驱。这时网络中必存它们都有直接前驱。这时网络中必存它们都有直接前驱。这时网络中必存在有向环。在有向环。在有向环。在有向环。输入输入输入输入AOVAOV网络；网络；网络；网络；在在在在AOVAOV网络中选一个网络中选一个网络中选一个网络中选一个没有直接前驱没有直接前驱的顶点的顶点的顶点的顶点,并输出之并输出之并输出之并输出之;从图中删去该顶点从图中删去该顶点从图中删去该顶点从图中删去该顶点,同时删去所有它发出的有向边同时删去所有它发出的有向边同时删
9、去所有它发出的有向边同时删去所有它发出的有向边;abhcdgfe得到的拓扑有序序列满足图中给出的所有前驱和后继关系。得到的拓扑有序序列满足图中给出的所有前驱和后继关系。得到的拓扑有序序列满足图中给出的所有前驱和后继关系。得到的拓扑有序序列满足图中给出的所有前驱和后继关系。如何在计算机上实现如何在计算机上实现如何在计算机上实现如何在计算机上实现对有向图的拓扑排序？对有向图的拓扑排序？对有向图的拓扑排序？对有向图的拓扑排序？在算法中需要用定量的描述替代定性的概念在算法中需要用定量的描述替代定性的概念 没有前驱的顶点没有前驱的顶点 入度为零的顶点入度为零的顶点删除顶点及以它为尾的弧删除顶点及以它为尾
10、的弧 弧头顶点的入度减弧头顶点的入度减1拓扑排序算法拓扑排序算法拓扑排序算法拓扑排序算法拓扑排序方法拓扑排序方法拓扑排序方法拓扑排序方法 拓扑排序过程中涉及的数据和操作：拓扑排序过程中涉及的数据和操作：拓扑排序过程中涉及的数据和操作：拓扑排序过程中涉及的数据和操作：（1 1 1 1）选择一入度为选择一入度为选择一入度为选择一入度为0 0 0 0顶点顶点顶点顶点v v v v，输出；输出；输出；输出；（2 2 2 2）将将将将v v v v邻接到的顶点的入度减邻接到的顶点的入度减邻接到的顶点的入度减邻接到的顶点的入度减1 1 1 1；（3 3 3 3）重复（）重复（）重复（）重复（1 1 1 1
11、）、（）、（）、（）、（2 2 2 2），），），），直到输出全部顶点，直到输出全部顶点，直到输出全部顶点，直到输出全部顶点，或，有向图没有入度为或，有向图没有入度为或，有向图没有入度为或，有向图没有入度为0 0 0 0的顶点。的顶点。的顶点。的顶点。数据：数据：数据：数据：有向图、顶点的入度；有向图、顶点的入度；有向图、顶点的入度；有向图、顶点的入度；操作：操作：操作：操作：（1 1）选择一入度为选择一入度为选择一入度为选择一入度为0 0顶点顶点顶点顶点v v，输出；输出；输出；输出；（2 2）将将将将v v邻接到的顶点邻接到的顶点邻接到的顶点邻接到的顶点 u u 的入度减的入度减的入度减的
12、入度减1 1。为算法的有关数据选择设计存储结构为算法的有关数据选择设计存储结构为算法的有关数据选择设计存储结构为算法的有关数据选择设计存储结构(图用图用图用图用邻接表表示邻接表表示邻接表表示邻接表表示)C0C1C2C3C4C5 C0 C1 C2 C3 0 C4 C5 0data firstarcdata firstarc 1 3 0 5 1 5 0 0 1 5 00数组数组数组数组indegreeindegreeindegreeindegree：记录各顶点入度记录各顶点入度记录各顶点入度记录各顶点入度0 01 12 23 34 45 5130103indegreeindegree对于入度为零的
13、顶点即无前驱顶点，删除该顶点及以它为尾对于入度为零的顶点即无前驱顶点，删除该顶点及以它为尾对于入度为零的顶点即无前驱顶点，删除该顶点及以它为尾对于入度为零的顶点即无前驱顶点，删除该顶点及以它为尾的弧的操作，则可换以弧头顶点的入度减的弧的操作，则可换以弧头顶点的入度减的弧的操作，则可换以弧头顶点的入度减的弧的操作，则可换以弧头顶点的入度减1 1 1 1来实现。来实现。来实现。来实现。C0C1C2C3C4C5S.baseS.baseS.baseS.base6 6 6 65 5 5 54 4 4 43 3 3 32 2 2 21 1 1 10 0 0 04 4 4 42 2 2 2S.topS.to
14、pS.topS.top 栈栈栈栈S S S S：存储入度为存储入度为存储入度为存储入度为0 0 0 0的顶点的编号的顶点的编号的顶点的编号的顶点的编号.初始时，只有初始时，只有v2,v4v2,v4两顶点的入度为两顶点的入度为0 0C0C1C2C3C4C5 为避免每次都要搜索入度为零的顶点，在算法中设置一个为避免每次都要搜索入度为零的顶点，在算法中设置一个“栈栈”，以保存，以保存“入度为零入度为零”的顶点。的顶点。u 如果输出顶点个数少于如果输出顶点个数少于如果输出顶点个数少于如果输出顶点个数少于AOVAOV网络的顶点个数网络的顶点个数网络的顶点个数网络的顶点个数,则报告网络中存在有向环。则报告
15、网络中存在有向环。则报告网络中存在有向环。则报告网络中存在有向环。拓扑排序算法描述：拓扑排序算法描述：拓扑排序算法描述：拓扑排序算法描述：u建立入度为零的顶点栈建立入度为零的顶点栈建立入度为零的顶点栈建立入度为零的顶点栈;u当入度为零的顶点栈不空时当入度为零的顶点栈不空时当入度为零的顶点栈不空时当入度为零的顶点栈不空时,重复执行：重复执行：重复执行：重复执行：l l 从顶点栈中退出一个顶点从顶点栈中退出一个顶点从顶点栈中退出一个顶点从顶点栈中退出一个顶点,并输出之；并输出之；并输出之；并输出之；l l 从从从从AOVAOVAOVAOV网络中删去这个顶点和它发出的边网络中删去这个顶点和它发出的边
16、网络中删去这个顶点和它发出的边网络中删去这个顶点和它发出的边,边的终顶点入度减边的终顶点入度减边的终顶点入度减边的终顶点入度减1 1 1 1；l l如果边的终顶点入度减至如果边的终顶点入度减至如果边的终顶点入度减至如果边的终顶点入度减至0,0,0,0,则该顶点进入度为零的顶点栈。则该顶点进入度为零的顶点栈。则该顶点进入度为零的顶点栈。则该顶点进入度为零的顶点栈。Status TopologicalSort(ALGraph G)/若若G无回路，则输出无回路，则输出G的顶点的一个拓扑序列并返回的顶点的一个拓扑序列并返回OK，否则否则ERROR FindInDegree(G,indegree);/求
17、各顶点入度求各顶点入度indegree0.vexnum-1 InitStack(S);for(i=0;inextarc)k=p-adjvex;if(!(-indegreek)Push(S,k);/for /while0 01 12 23 34 45 5130103indegreeindegree栈栈栈栈S S S S5 5 5 54 4 4 43 3 3 32 2 2 21 1 1 10 0 0 04 4 4 42 2 2 2i=44,C4count=1pk=00 00 0k=12 2k=52 2p=NULL C0 C1 C2 C3 C4 C5 data firstarcdata firsta
18、rc 1 3 5 1 5 0 1 5 0 01 12 23 34 45 5while(!StackEmpty(S)Pop(S,i);printf(i,G.verticesi.data);+count;for(p=G.verticesi.firstarc;p;p=p-nextarc)k=p-adjvex;if(!(-indegreek)Push(S,k);/for /while0 01 12 23 34 45 5020102indegreeindegree栈栈栈栈S S S S5 5 5 54 4 4 43 3 3 32 2 2 21 1 1 10 0 0 00 0 0 02 2 2 2i=00
19、,C0count=2pk=11 13 3k=30 0p=NULL C0 C1 C2 C3 C4 C5 data firstarcdata firstarc 1 3 5 1 5 0 1 5 0 01 12 23 34 45 5while(!StackEmpty(S)Pop(S,i);printf(i,G.verticesi.data);+count;for(p=G.verticesi.firstarc;p;p=p-nextarc)k=p-adjvex;if(!(-indegreek)Push(S,k);/for /while0 01 12 23 34 45 5010002indegreeinde
20、gree栈栈栈栈S S S S5 5 5 54 4 4 43 3 3 32 2 2 21 1 1 10 0 0 03 3 3 32 2 2 2i=33,C3count=3pp=NULL C0 C1 C2 C3 C4 C5 data firstarcdata firstarc 1 3 5 1 5 0 1 5 0 01 12 23 34 45 5while(!StackEmpty(S)Pop(S,i);printf(i,G.verticesi.data);+count;for(p=G.verticesi.firstarc;p;p=p-nextarc)k=p-adjvex;if(!(-indegre
21、ek)Push(S,k);/for /while0 01 12 23 34 45 5010002indegreeindegree栈栈栈栈S S S S5 5 5 54 4 4 43 3 3 32 2 2 21 1 1 10 0 0 02 2 2 2i=22,C2count=4pk=10 01 1k=51 1p=NULL C0 C1 C2 C3 C4 C5 data firstarcdata firstarc 1 3 5 1 5 0 1 5 00 01 12 23 34 45 5while(!StackEmpty(S)Pop(S,i);printf(i,G.verticesi.data);+co
22、unt;for(p=G.verticesi.firstarc;p;p=p-nextarc)k=p-adjvex;if(!(-indegreek)Push(S,k);/for /while0 01 12 23 34 45 5000001indegreeindegree栈栈栈栈S S S S5 5 5 54 4 4 43 3 3 32 2 2 21 1 1 10 0 0 01 1 1 1i=11,C1count=5pk=50 05 5p=NULL C0 C1 C2 C3 C4 C5 data firstarcdata firstarc 1 3 5 1 5 0 1 5 0 01 12 23 34 4
23、5 5while(!StackEmpty(S)Pop(S,i);printf(i,G.verticesi.data);+count;for(p=G.verticesi.firstarc;p;p=p-nextarc)k=p-adjvex;if(!(-indegreek)Push(S,k);/for /while0 01 12 23 34 45 5000000indegreeindegree栈栈栈栈S S S S5 5 5 54 4 4 43 3 3 32 2 2 21 1 1 10 0 0 05 5 5 5i=55,C5count=6pp=NULL C0 C1 C2 C3 C4 C5 data
24、firstarcdata firstarc 1 3 5 1 5 0 1 5 0 01 12 23 34 45 5 C0 C1 C2 C3 C4 C5 data firstarcdata firstarc 1 3 5 1 5 0 1 5 拓扑序列：拓扑序列：C4,C0,C3,C2,C1,C5 C0C1C2C3C4C5Status TopologicalSort(ALGraph G)FindInDegree(G,indegree);/求各顶点入度求各顶点入度indegree0.vexnum-1 InitStack(S);for(i=0;inextarc)k=p-adjvex;if(!(-indegreek)Push(S,k);/对对i号顶点邻接到的号顶点邻接到的 每个顶点入度减每个顶点入度减1 /若入度减为若入度减为0，则入栈，则入栈 /for /while if(countG.vexnum)return ERROR;/该有向图有回路该有向图有回路 else return OK;/TopologicalSort/输出输出i号顶点的数据，并计数号顶点的数据，并计数/从零入度顶点栈从零入度顶点栈S 栈顶，获得一入度为零的顶点栈顶，获得一入度为零的顶点icount=6v2v4v1v5v3v6自测题自测题 AOV-AOV-网的拓扑排序网的拓扑排序v2v4v1v5v3v6