首页 > 试题广场 > 以下哪些算法可以检测一个有向图中是否存在环( )
[不定项选择题]

以下哪些算法可以检测一个有向图中是否存在环( )

  • 深度优先遍历
  • 广度优先遍历
  • 拓扑排序
  • 关键路径算法
简单说一下算法步骤,为什么选DFS和拓扑排序:
DFS的时候,如果要访问的元素已经访问过,它在当前的栈内还没出栈,那么就是有环。BFS不行是因为可能有多个节点指向该节点,不一定是因为有环。
拓扑排序会循环执行以下两步:
(1) 选择一个入度为0的顶点,输出
(2) 从图中删除此顶点以及所有的出边
循环结束后,若输出的顶点数小于网中的顶点数,则说明有回路


发表于 2019-08-04 17:26:09 回复(0)
拓扑排序。。想都不用想这玩意的存在就是为了检查有无环。。
深度优先遍历。。尽可能深的搜索树的分支。。查着查着肯定有环的存在。。
发表于 2019-05-14 15:46:55 回复(0)

热门推荐