Spa*_*dan 6 algorithm graph depth-first-search topological-sort
对于无向图,如果我们需要找到一个循环,我们使用深度优先搜索,如这个较老的问题所述,这是一个众所周知的方法,也是最优的.
但对于有向图,另一个问题建议使用拓扑排序.
我的问题是,为什么我们不能使用我们用于无向图的相同技术来检查有向图中的周期？我已经想到了各种情况,算法似乎总是同意.
任何人都可以提出一些示例有向图,其中DFS无法找到一个循环,但拓扑排序呢？
您的问题似乎如下:您可以使用深度优先搜索来检测无向图中的周期,还是应该使用拓扑排序？
答案是两种方法都有效.如果有向图中存在循环,则可以通过在图上运行深度优先搜索来检测此循环.一旦从循环中的节点开始搜索,就可以保证最终发现循环.
事实证明拓扑排序和DFS在以下方面密切相关:如果您在图中运行DFS并且没有找到循环,那么将每个节点标记为完全探索的相反顺序将给出拓扑一种图表.换句话说,"使用拓扑排序"的解决方案和"使用DFS"的解决方案可以被认为是非常相似的算法,因为实现拓扑排序的一种方法是使用DFS.
希望这可以帮助!
| 归档时间： |
|
| 查看次数： |
4515 次 |
| 最近记录： |