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

Poj1094拓扑排序总结

2013年09月09日 ⁄ 综合 ⁄ 共 309字 ⁄ 字号 评论关闭

   这道题目不是什么难题,但是我做了蛮长时间。主要是刚开始会有各种困难。

   算法其实不难,就是先拓扑排序,排序过程中可以检查环路,没有环路之后检查排序节点是否都依次相连。拓扑排序与回路判断的算法:可以用DFS,在顶点第一次被访问时标记(1),其下顶点都被访问后再次标记(-1),并且将其“退栈顺序”记录下来,退栈顺序就是拓扑序,而访问过程中遇到标记为1的顶点就说明有回路。这个算法利用了DFS产生的深度遍历树的性质,深度优先树真是一棵神奇的树啊。有一个缺陷是,我现在还没办法不用递归来实现这个算法,也就是用栈还没办法实现。利用度的标记。这一算法非常简单明了,但算法复杂度比DFS高。本题采用这一算法可以在短时间内AC。

抱歉!评论已关闭.