拓扑排序和关键路径课件.ppt

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

1、拓扑排序和关键路径一、拓扑排序算法在日常生活中，一项大的工程可以看作是由若干个子工程（这些子工程称为“活动”）组成的集合，这些子工程（活动）之间必定存在一些先后关系，即某些子工程（活动）必须在其它一些子工程（活动）完成之后才能开始，我们可以用有向图来形象地表示这些子工程（活动）之间的先后关系，子工程（活动）为顶点，子工程（活动）之间的先后关系为有向边，这种有向图称为“顶点活动网络”，又称“AOV网”。在AOV网中，有向边代表子工程（活动）的先后关系，即有向边的起点活动是终点活动的前驱活动，只有当起

2、点活动完成之后终点活动才能进行。如果有一条从顶点Vi到Vj的路径，则说Vi是Vj的前驱，Vj是Vi的后继。如果有弧，则称Vi是Vj的直接前驱，Vj是Vi的直接后继。一个AOV网应该是一个有向无环图，即不应该带有回路，否则必定会有一些活动互相牵制，造成环中的活动都无法进行。把不带回路的AOV网中的所有活动排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，这个过程称为“拓扑排序”，所得到的活动序列称为“拓扑序列”。常州市第一中学林厚从拓扑排序和关键路径一、拓扑排序算法需要注

3、意的是AOV网的拓扑序列是不唯一的，如对下图进行拓扑排序至少可以得到如下几种拓扑序列：02143567、01243657、02143657、01243567。在上图所示的AOV网中，工程1和工程2显然可以同时进行，先后无所谓；但工程4却要等工程1和工程2都完成以后才可进行；工程3要等到工程1和工程4完成以后才可进行；工程5又要等到工程3、工程4完成以后才可进行；工程6则要等到工程4完成后才能进行；工程7要等到工程3、工程5、过程6都完成后才能进行。可见由AOV网构造拓扑序列具有很高的实际应用价值。

4、常州市第一中学林厚从拓扑排序和关键路径一、拓扑排序算法构造拓扑序列的拓扑排序算法思想很简单：只要选择一个入度为0的顶点并输出，然后从AOV网中删除此顶点及以此顶点为起点的所有关联边；重复上述两步，直到不存在入度为0的顶点为止，若输出的顶点数小于AOV网中的顶点数，则输出“有回路信息”，否则输出的顶点序列就是一种拓扑序列。常州市第一中学林厚从拓扑排序和关键路径一、拓扑排序算法对上图进行拓扑排序的过程如下：1、选择顶点0（唯一），输出0，删除边<0，1>，<0，2>；2、选择顶点1（不唯一，可选顶点2

5、），输出1，删除边<1，3>，<1，4>；3、选择顶点2（唯一），输出2，删除边<2，4>；4、选择顶点4（唯一），输出4，删除边<4，3>，<4，5>，<4,6>；5、选择顶点3（不唯一，可选顶点6），输出3，删除边<3，5>，<3，7>；6、选择顶点5（不唯一，可选顶点6），输出5，删除边<5，7>；7、选择顶点6（唯一），输出6，删除边<6，7>；8、选择顶点7（唯一），输出7，结束。常州市第一中学林厚从拓扑排序和关键路径一、拓扑排序算法思考：拓扑排序一般用在哪些场合呢？解答：如判回路或图的

6、动态规划过程中分阶段。常州市第一中学林厚从拓扑排序和关键路径二、关键路径算法常州市第一中学林厚从拓扑排序和关键路径二、关键路径算法利用AOV网络，对其进行拓扑排序能对工程中活动的先后顺序作出安排。但一个活动的完成总需要一定的时间，为了能估算出某个活动的开始时间，找出那些影响工程完成时间的最主要的活动，我们可以利用带权的有向图，图中的边表示活动，边上的权表示完成该活动所需要的时间，一条边的两个顶点分别表示活动的开始事件和结束事件，这种用边表示活动的网络，称为“AOE网”。其中，有两个特殊的顶点（事件

7、），分别称为源点和汇点，源点表示整个工程的开始，通常令第一个事件（事件1）作为源点，它只有出边没有入边；汇点表示整个工程的结束，通常令最后一个事件（事件n）作为汇点，它只有入边没有出边；其余事件的编号为2到n-1。常州市第一中学林厚从拓扑排序和关键路径二、关键路径算法在实际应用中，AOE网应该是没有回路的，并且存在唯一的入度为0的源点和唯一的出度为0的汇点。下图表示一个具有12个活动的AOE网。图中有8个顶点，分别表示事件0到7，其中，0表示开始事件，7表示结束事件，边上的权表示完成该活动所需要的

8、时间。AOE网要研究的问题是完成整个工程至少需要多少时间？哪些活动是影响工程进度的关键？常州市第一中学林厚从拓扑排序和关键路径二、关键路径算法下面先讨论一个事件的最早发生时间和一个活动的最早开始时间。如下图，事件Vj必须在它的所有入边活动eik（1≤k≤n）都完成后才能发生。活动eik（1≤k≤n）的最早开始时间是与它对应的起点事件Vik的最早发生时间。所有以事件Vj为起点事件的出边活动ejk（1≤k≤m）的最早开始时间都等于事件Vj的最早发生时间。所以，我们可以从源点出发按照上述