拓扑排序和关键路径.ppt

《拓扑排序和关键路径.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、AOV网-拓扑排序有向无环图及其应用AOE网-关键路径有向无环图小结和作业有向无环图的应用公用表达式有向无环图一、定义：一个无环的有向图，称为有向无环图（DAG图）V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8DAG图有环的有向图DAG=DirectedAcyclicGraph有向无环图二、如何判断一个图是否是DAG？V1V2V4V5V3V7V6V8DAG图V1V2V3V8V7V6V5V4V1V2V4V5V3V7V6V8非DAG图V1V2V3V8V7V6V5V4有向无环图二、如何判断一个图是否是DAG？深度优先搜索没有出现指向祖先的回边，即：没有一个顶点有一条

2、边，指向遍历过程中先访问过的顶点（并且这些顶点的DFS函数没有执行完）有向无环图boolDAG(GraphG){for(v=0;v

3、UE;Push(S,v);for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){{if(winS)thenreturn(FALSE);//有回边if(!visited[w]){if(!DFS-DAG(G,w))return(FALSE);}Pop(S,v);//v的所有邻接点已经遍历完return(TRUE);}//DFS-T公用表达式用树表示表达式：((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)*****+++++cccdddeebba公用表达式多次出现的变量和表达式通过共用，减少出现次数*****+++++

4、cccdddeebba****+++cdeba拓扑排序一、定义由集合上的一个偏序关系得到集合的全序关系的操作偏序：自反的、反对称的、传递的全序：R是集合X上的偏序，对于集合X中的任何元素x,y，如果都有xRy或者yRx,则称R是全序关系拓扑排序BDACBDAC偏序就是集合中的部分成员可以比较。全序是集合中的任何成员之间都可以比较。偏序全序拓扑排序按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列拓扑排序用顶点表示活动，弧表示活动间的优先关系的有向图。AOV网（Activ

5、ityOnVertexNetWork）AOV网中不应该出现有向环：如果存在环，则某项活动以自己为先决条件，拓扑排序BDAC可求得拓扑有序序列：ABCD或ACBDBDAC不能求得它的拓扑有序序列。因为图中存在一个回路{B,C,D}拓扑排序拓扑排序---方法11、从有向图中选取一个没有前驱的顶点，并输出之;2、从有向图中删去此顶点以及所有以它为尾的弧;3、重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。拓扑排序---方法1acgbdhfebhacdgfe拓扑序列：在算法中需要用定量的描述替代定性的概念没有前驱的顶点入度为零的顶点删除顶点及以它为尾的弧弧头顶点的入度减1拓

6、扑排序---方法1StatusToplogicalSort(ALGraghG){FindInDegree(G,indegree);InitStack(S);for(i=0;i

7、Pop(S,v);++count;printf(v);for(w=FirstAdj(v);w;w=NextAdj(G,v,w)){--indegree(w);//弧头顶点的入度减1if(!indegree[w])Push(S,w);}//for}//while………………}拓扑排序---算法总的时间复杂度：O(n+e)算法分析：拓扑排序---算法拓扑排序---方法2acgbdhfebhacdgfe拓扑序列：对有向无环图利用深度优先搜索进行拓扑排序。拓扑排序---方法2acgbdhfebhac