首页 > 编程语言 > 详细

拓扑排序

时间:2015-05-08 19:55:05      阅读:216      评论:0      收藏:0      [点我收藏+]

用两种方式来实现

1、 深度优先搜索(DFS)

对有向图采取深度优先搜索,并且在postVist处,打印所访问的节点。最后打印出的字符序列的反序列正好满足拓扑排序。(可以在postVist()方法中,将所访问的元素压到栈中,这样最后从栈中一个个弹出来的元素的序列恰好就是拓扑排序的一个解)

这种方法证明是正确的,虽然感觉起来比较怪。

2. 根据节点入度排序

(1)选择一个入度为0的节点N,并输出它。(肯定会有入度为0的,就是起点)

(2)从图中删除N,并且删掉从N出发的所有有向边(即把与N相邻的顶点的入度分别减1)

(3)重复(1)(2),直到剩余的顶点中没有入度为0的顶点为止

拓扑排序

原文:http://www.cnblogs.com/james6176/p/4488415.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!