频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
图(3)--拓扑排序与关键路径
2014-02-20 11:15:55         来源:图(3)--拓扑排序与关键路径  
收藏   我要投稿

一.拓扑排序:

1.定义: 拓扑排序可以理解为在有向图无环图AOV-网(Activity On Vertex :用图的顶点表示活动,用弧表示活动之间的优先级)中排成一个具有前后次序的线性序列。

2.实现方式:

1). 输入AOV网络。令 n 为顶点个数。
2). 在AOV网络中选一个没有直接前驱的顶点, 并输出之;
3). 从图中删去该顶点, 同时删去所有它发出的有向边;
4). 重复以上 2、3 步, 直到:
全部顶点均已输出,拓扑有序序列形成,拓扑排序完成

或者,图中还有未输出的顶点,但已跳出处理循环。这说明图中还剩下一些顶点,它们都有直接前驱,再也找不到没有前驱的顶点了。这时AOV网络中必定存 在有向环。

3.算法实现:

Status Topological Sort(ALGraph G)
{
	       //采用邻接表存储结构。若G无回路,则输出拓扑序列并返回OK,否则ERROR
	        FindInDegree(G,indegree); //对各顶点求入度indegree[0..vernum-1]
		InitStack(S);  //建零入度顶点栈
		for(i=0;inextarc)
		     {          
			   k=p—>apex;//对i号顶点的每个邻接点入度减1           
			   if(!(--indegree[k]))  Push(S,k);   //若入度减为0,则入栈    
	              }//for   
		}//while   
		if(count

二.关键路径(操作带权的有向AOE-网(Activity on Adge:用边表示活动,边上的权值表示活动持续的时间,顶点表示事件,事件表示在它之前的活动全都完成了)):

1.关键路径:完成工程最短的时间是从开始点(原点)到结束点(汇点)的最长路径长度,路径最长的路径叫做关键路径。

\

从v1到v9的最长路径是(v1,v2,v5,v8,v9),路径长度是18,故(v1,v2,v5,v8,v9)是一条关键路径<喎"https://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+ICAgICAgICAgICAgICAgMi652Lz8u+62rzpsKGkpPWUoaSksvLTX7tTnv6rKvMqxvOS6zdfuze2/qsq8yrG85M/gtci1xLvutq+jrLnYvPzCt762yc+1xMv509C77ravtrzKx7nYvPy77ravo6zS8rTLzOHHsM3qs8m3x7nYvPy77ravsqKyu8TczOG437mks8y1xL34tsg8L3A+CjxwPiAgICAgICAgICAgICAgICAgICAgICAgIMD9yOc6YTa1xNfu1Oe/qsq8yrG85GUoYTYpPTUs1+7N7b+qyrzKsbzkzqpsKGE2KT04LNLizrbXxWE2zcaz2TPM7M3qs8nSsrK7u+HTsM/suaSzzLXEvfi2yKOsy/nS1LfWzvbExNCpyse52Lz8u+62r72r09DA+9Pay/W2zNX7uPa5pMbaoaM8L3A+CjxwPiAgICAgICAgICAgICAgICAgICAgICAgIM3GwO3U9dH5x/O52Lz8u+62ryy8tNXSbChpKT1lKGkptcS77ravo7o8L3A+CjxwPiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICDJ6Lvutq9hadPJu6E8aixrPrHtyr6jrMbks9bQ+MqxvOTOqmR1dCg8aixrPiksucrT0KO6PC9wPgo8cD4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGUoaSk9dmUoaikgICAgICAgICAgICAgKHZlKGopse3KvraltePKwrz+arXE1+7U57+qyrzKsbzkKTwvcD4KPHA+ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbChpKT12bChrKS1kdXQoPGosaz4pICAgICh2bChrKbHtyr62pbXjysK8/mu1xNfuze2/qsq8yrG85CkgPC9wPgo8cD4gICAgICAgICAgICAgICAgICAgICAgICAgz9bU2r7N0qrH83ZlKGopus12bChqKaOst9bBvbK9vfjQ0Do8L3A+CjxwPiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKDEptNN2ZSgwKT0wz/LHsLXdzcY6dmUoaik9TWF4e3ZlKGkpJiM0MztkdXQoPGksaj4pfSAgICAgIDxpLGo+yvTT2lQoy/nT0NLUtdpquPa2pbXjzqrNt7XEu6G1xLyvus8pPC9wPgo8cD4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICgyKbTTdmwobi0xKT12ZShuLTEpIM/yuvO13c3GOnZsKGkpPU1pbnt2bChqKS1kdXQoPGksaj4pfSAgICAgIDxpLGo+yvTT2lMoy/nT0NLUtdppuPa2pbXjzqrOsrXEu6G1xLyvus8pPC9wPgo8cD4gICAgICAgICAgICAgICAgICAgICAgICDT2srHztLDx7/J0tS1w7W9x/O52Lz8u+62r7XEy7zP68jnz8KjujwvcD4KPHA+ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAxo6nK5MjrZcz1u6GjqGmjrGqjqaOsvajBokFPRc34tcS05rSiveG5uaGjPGJyPgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDKjqbTT1LS143Yws/a3oqOswe52ZVswXaO9MLC0zdjGy9PQ0PLH88bk0+C497alteO1xNfu1Oe3osn6yrF2ZVtpXaOoMaHcaaHcIG4tMaOpoaPI57n7tcO1vbXEzdjGy9PQ0PLQ8sHQ1tC2pbXjuPbK/dCh09rN+NbQtqW148r9bqOs1PLLtcP3zfjW0CAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgtObU2ru3o6yyu8Tcx/O52Lz8wre+tqOsy+O3qNbV1rmju7fx1PLWtNDQsr3W6KOoM6OpoaM8YnI+CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMyCjqbTTu+O143Zus/a3oqOswe52bFtuLTFdPSB2ZVtuLTFdo6ywtMTmzdjGy9PQ0PLH88bk0+C497alteO1xNfus9m3osn6yrG85HZsW2ldIChuLTIgod1pod0gMimjuzxicj4KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICA0o6m4+b7duPe2pbXjtcR2ZbrNdmwmIzIwNTQwO6Osx/PDv8z1u6FztcTX7tTnv6rKvMqxvORlKHMpus3X7rPZv6rKvMqxvORsKHMpoaPI9MSzzPW7ocL61+PM9bz+ZShzKT1sKHMpo6zU8s6qudi8/Lvutq+hoyAgICAgICAgICAgICAgICAgIDwvcD4KPHA+ICAgICAgICAgICAgICAgIDMuwPvTw8nPyvbLvM/rveLM4qO6PC9wPgo8cD4gICAgICAgICAgICAgICAgICAgICAgPGltZyBzcmM9"https://www.2cto.com/uploadfile/Collfiles/20140220/20140220083711119.jpg" alt="\">

通过已经求得的各个顶点的ve(i)和vl(i)来求活动的e(i)和l()

由于关键活动为e(i)=l(i),所以可得a1,a4,a7,a8,a10,a11为关键活动,相应的V1->V2->V5->V7->V9和V1->V2->V5->V8->V9为关键路径

4.总结求关键路径的方法:

第一步(求每个顶点事件的最早开始时间): ve(源点) = 0 ;
ve(j) = Max{ ve(i) + dut()}

第二步(求每个顶点的最晚开始时间): vl(汇点) = ve(汇点);
vl(i) = Min { vl(j) – dut()}

第三步(求每个活动的最早开始时间和最晚开始时间): e(s)= ve(i)
l(s)= vl(j) - dut()

点击复制链接 与好友分享!回本站首页
相关TAG标签 拓扑 路径 关键
上一篇:angular + easyui 做界面验证
下一篇:设计模式16——行为型模式之解释器模式
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站