下面哪些方法可以判断一个有向图是否有环(回路)?()A.深度优先遍历B.拓扑排序C.求最短路
遍历,拓扑,回路
已帮助 人
-
正确答案:AB
检查有向图是否有环的方法不仅仅只有拓扑排序,还可以通过深度优先遍历。判断方法的基本思想如下:我们用堆栈对有向图进行深度优先遍历,遍历过程中,我们随时判断堆栈里是否存在同一个结点被两次压入到堆栈的情形,如果有的话,则该图有环,跳出程序;如果遍历结束都没有跳出,则没有环。
