(简答题)
对于一个有向图,不用拓扑排序,如何判定图中是否存在环?
正确答案
对于无向图,如果在深度优先遍历中遇到回边,则必定存在环。对于有向图,如果从有向图的某个顶点v出发的遍历,在DFS(v)结束之前出现了一条从顶点u指向v的回边,则此有向图必定存在环。因为u在深度优先生成树上是v的子树,即存在u到v的路径,现在又出现一条从u指向v的弧,则它们必然构成一条回路。
答案解析
略
相似试题
(单选题)
判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以用()。
(单选题)
判定一个有向图是否存在回路,除了可以利用拓扑排序的方法外,还可以利用()。
(判断题)
对一个有向图进行拓扑排序,一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。
(单选题)
对于一个具有n个顶点和e条边的无向图,进行拓扑排序时,总的时间为()
(判断题)
有回路的有向图不能完成拓扑排序。
(单选题)
下面有向图所示的拓扑排序的结果序列是()。
(简答题)
已知有向图如下所示,请写出该图所有的拓扑序列。
(单选题)
任一个有向图的拓扑序列()。
(填空题)
如果一个有向图不存在(),则该图的全部顶点可以排列成一个拓扑序列。