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