有向图最短Cycle

jy_121 发表于 2019-4-8 11:29
能详细说下如何dfs吗，O(V + E)的话怎么能在遍历时避免重复访问又记录环路呢？谢谢

dfs O(v+e) 做不到求出最短环路吧？可以做到检测是否有环路 求最短环路的话需要在回溯的时候把visited标记去掉

lz4321234 发表于 2019-9-7 01:40
dfs O(v+e) 做不到求出最短环路吧？可以做到检测是否有环路 求最短环路的话需要在回溯的时候把visited标 ...

我也是这么想的 如果dfs的话就需要把所有可能的路径都要走一遍 那么如果是这样的话 时间复杂度是多少？

umialpha 发表于 2019-4-8 18:22
visit=0(not visit) 1 visiting 2 visited
def cycle(node)
     if visit[node]==visiting:return true ...

你这个思路是错误的吧 因为你这样做了的话 如果有一个node存在于好几个环之中怎么办

yl2762 发表于 2019-03-13 09:07:23
可不可以这样：用Queue做广度优先搜索直到遍历到自身结点，就是最短。另外在加到queue的时候把bfs的parent结点也一起存，这样在bfs结束以后可以不断找parent得到路径，最后再把路径反转

我觉得这个是最容易想的，大家觉得呢？