网友您好， 请在下方输入框内输入要搜索的题目：
题目内容
（请给出正确答案）
对于一个有向图，除了拓扑排序的方法外，还可以通过对有向图进行深度优先遍历的方法来判断有向图是否有回路存在。
参考答案和解析
对于无向图，如果在深度优先遍历中遇到回边，则必定存在环。对于有向图，如果从有向图的某个顶点v出发的遍历，在DFS(v)结束之前出现了一条从顶点u指向v的回边，则此有向图必定存在环。因为u在深度优先生成树上是v的子树，即存在u到v的路径，现在又出现一条从u指向v的弧，则它们必然构成一条回路。
更多 “对于一个有向图，除了拓扑排序的方法外，还可以通过对有向图进行深度优先遍历的方法来判断有向图是否有回路存在。” 相关考题
考题
采用邻接表存储的图的深度优先遍历算法类似于树的(22)，用邻接表存储的图的广度优先遍历算法类似于树的(23)，判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用(24)。A．中序遍历B．先序遍历C．后序遍历D．按层次遍历
考题
问答题对于一个有向图，不用拓扑排序，如何判定图中是否存在环？
热门标签
最新试卷