数据结构，为什么？详解！下面（）方法可以判断出一个有向图是否有环。A．深度优先遍历B．拓扑排序C．求最短路径D．求关键路径

Question

数据结构，为什么？详解！
下面（ ）方法可以判断出一个有向图是否有环。
A．深度优先遍历 B．拓扑排序 C．求最短路径 D．求关键路径

Answer 1

AB
－－－－－－－－－－－－－－－－－－－－－－－
判断有否环，就是要知道 if( v0 == vm)
即判断 某一个点和查找过程中的另一个点，是否是同一个点
我的想法是这样的，希望和大家交流下..
1.［深度优先遍历］的概念：
假定每一个点都没被访问过。从起点开始，找邻接的点。
对每个点，只要存在有向的路径，查找就可以继续，顺藤摸瓜（同时把经过的点给标记成“已访问”）。一旦遇到“已访问”就表示，有环路。
2.［拓扑］，一般判断环路都靠它
任一有向无环图，必定有拓扑排序（有可能多个）
所以如果拓扑排序成功，则无环路；排序失败，则有环路
3.［求最短路径］的算法很多，
Dijkstra算法,SPFA算法,Floyd-Warshall算法,Johnson算法,Bellman-Ford算法..
我想这里指的是Dijkstra算法吧，
Dijkstra解决的问题是：指定起始点，计算它到图中各点的最小路径。条件是图中无负权。
Dijkstra的想法是“最短路径的前缀一定是最短路径”，于是有环的路径肯定被剔除，但是被剔除的不一定都有环啊，所以没法直接判断这整个图有没有环。
4.［求关键路径］
求关键路径的前提是无环...
一般求关键路径之前会先用［拓扑］验证一下是否有环
5.［广度优先搜索］
广度优先搜索，好比树的层次遍历。
在有向图中，广度优先搜索不能判断环路 —— 无法通过判断“已访问”而断定回路。