现在的位置: 首页 > 综合 > 正文

算法导论22.4-5 构造拓扑排序

2018年03月22日 ⁄ 综合 ⁄ 共 191字 ⁄ 字号 评论关闭

题目要求用非DFS得方法构造拓扑排序。

找出入度为0的节点,删除该点并删除该点所有的出边。

删除的顺序就是拓扑排序的顺序。要求复杂度O(V + E)。

 方案:

1. 遍历邻接表一遍,统计每个元素的入度。(O(E))

2. 找出一个入度为0的点u,将u的所有出边的目的点v的入度减一。(O(V + E))

3. 继续步骤一。


若G中包含回路:找不到入度为0的点,且G中仍然还有节点没有删除(剩下的就是G的回路)

抱歉!评论已关闭.