下面哪些方法可以判断一个有向图是否有环(回路)?()A.深度优先遍历B.拓扑排序C.求最短路

大学 遍历,拓扑,回路 已帮助 人

下面哪些方法可以判断一个有向图是否有环(回路)?()

A.深度优先遍历

B.拓扑排序

C.求最短路径

D.求关键路径

此题为多项选择题。请帮忙给出正确答案和分析,谢谢!

热搜:判断是否肾功能代偿期的标准有哪些

答案解析

难度★★☆ 搜索
  • 正确答案:AB
    检查有向图是否有环的方法不仅仅只有拓扑排序,还可以通过深度优先遍历。判断方法的基本思想如下:我们用堆栈对有向图进行深度优先遍历,遍历过程中,我们随时判断堆栈里是否存在同一个结点被两次压入到堆栈的情形,如果有的话,则该图有环,跳出程序;如果遍历结束都没有跳出,则没有环。