有向图最短Cycle

jy_121 发表于 2019/04/08 11:29:26


能详细说下如何dfs吗，O(V + E)的话怎么能在遍历时避免重复访问又记录环路呢？谢谢

visit=0(not visit) 1 visiting 2 visited
def cycle(node)
     if visit[node]==visiting:return true
     visit[node]=visiting
     flag=false
     for neighor in node.neighbors():
           flag |= cycle(neighbor)
     visit[node]= visted
     return flag
伪代码就是这样。

有个非常简单的做法。对于每条边(v1, v2)，check有没有v2->v1的路径。

v1 -> v*的connectivity可以跑一遍BFS复杂度是O(V+E)。两两的connectivity可以O(V * (V+ E))这么跑出来。所以总的复杂度是O(E + V*(V+E)) = O(V(V+E))

补充内容 (2019-4-8 19:37):
* check v2->v1路径的最短长度。这个bfs就能跑出来

有向图最短Cycle: dfs和floyd都可以

umialpha 发表于 2019-4-3 12:03
bfs很难写对，比如考虑这样一个很简单的例子(1,2), (1,3),(3,2) 在做bfs的时候que里是[1,2,3]在遍历3的时 ...

层主是假设没有给定起点是么？如果给定了起点，比如1的话，bfs就很简单

shannyhe 发表于 2019-4-30 00:30
层主是假设没有给定起点是么？如果给定了起点，比如1的话，bfs就很简单

请问该怎么写呢？

umialpha 发表于 2019-4-30 00:42
请问该怎么写呢？

想请问下BFS为什么比较难写呢? 题目是有向图的话你的这个例子不成立吧?

iiimisery 发表于 2019-6-15 07:52
想请问下BFS为什么比较难写呢? 题目是有向图的话你的这个例子不成立吧?

我的意思是很难判断是否有环。如果前提是一定有的话。拿就简单了。

umialpha 发表于 2019/06/18 11:51:17


我的意思是很难判断是否有环。如果前提是一定有的话。拿就简单了。

不好意思还是没太弄懂 如果没有环的话bfs也会因为queue为空返回-1吧？

多谢分享！

按照楼主给的参考, 题目要求是求全局最短环路吧？(多源点最短环路？)