回答以下关于图的问题：对于一个有向图，不用拓扑排序，如何判断图中是否存在环?

admin2014-10-20 109

问题回答以下关于图的问题：
对于一个有向图，不用拓扑排序，如何判断图中是否存在环?

选项

答案对于有向图进行深度优先遍历。如果从有向图上某个顶点v出发遍历，DFS(v)结束之前出现一条从顶点u到顶点v的回边，由于u在生成树上是v的子孙，则有向图中必定存在包含顶点v到顶点u的环。

解析

转载请注明原文地址:https://kaotiyun.com/show/w0vR777K

计算机科学与技术

相关试题推荐

随机试题

最新回复(0)