首页 > 试题广场 > 下面哪一个方法可以判断出一个有向图是否有环(  )。
[单选题]
下面哪一个方法可以判断出一个有向图是否有环(  )

  • 求最小生成树
  • 拓扑排序
  • 求最短路径
  • 求关键路径
选B
绝对能判断有向图是否有环的是:
1.DFS
2.拓扑排序
3.最短路径是允许有环的!C肯定不选。
4.D可选可不选。
 关键路径能不能判断一个图有环还存在一些争议。关键路径本身虽然不允许有环,但求关键路径的算法本身无法判断是否有环,判断是否有环的是关键路径的第一步——拓扑排序。所以这个问题的答案主要是看你从哪个角度出发看问题。
发表于 2020-06-29 10:35:20 回复(0)
B,拓扑排序就是在无环图才有解的
发表于 2020-06-05 11:11:32 回复(0)
B
发表于 2020-06-03 10:23:01 回复(0)