题目内容
(请给出正确答案)
[主观题]
对于一个有向图,除了拓扑排序的方法外,还可以通过对有向图进行深度优先遍历的方法来判断有向图是否有回路存在。
答案
对于无向图,如果在深度优先遍历中遇到回边,则必定存在环。对于有向图,如果从有向图的某个顶点v出发的遍历,在DFS(v)结束之前出现了一条从顶点u指向v的回边,则此有向图必定存在环。因为u在深度优先生成树上是v的子树,即存在u到v的路径,现在又出现一条从u指向v的弧,则它们必然构成一条回路。
如搜索结果不匹配,请 联系老师 获取答案