有向图最短Cycle

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

yl2762 发表于 2019-3-14 00:07
可不可以这样：用Queue做广度优先搜索直到遍历到自身结点，就是最短。另外在加到queue的时候把bfs的parent ...

bfs很难写对，比如考虑这样一个很简单的例子(1,2), (1,3),(3,2) 在做bfs的时候que里是[1,2,3]在遍历3的时候发现2已经遍历了，这个时候是有环还是没环呢？

补充内容 (2019-4-3 12:06):
dfs类似post-order-traverse。如果在访问后继节点时访问到了前驱节点，则一定有环。
bfs类似pre-order-traverse。在访问后继节点时访问到了前驱节点，你没法判断这个前驱节点一定有路径连接后继节点。

网上大多数方法应该还是用dfs，如果面试官不介意的话，可以用dfs找出所有的cycle取最短的那条。时间复杂度是O(V + E)

莫可可小姐 发表于 2019-3-21 05:31
搜了一下大家的做法，用floyd 写法比较简单，应该是O(n^3)， SCC写法比较难应该是O(V+E)约等于O(n^2)

can you elaborate it? Thanks!
Strong connected component is different from cycle.

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

搜了一下大家的做法，用floyd 写法比较简单，应该是O(n^3)， SCC写法比较难应该是O(V+E)约等于O(n^2)

tbian 发表于 2019-3-22 04:40
can you elaborate it? Thanks!
Strong connected component is different from cycle.

你是对的，我考虑错了，SCC不能解决这个问题

关于双倍积分奖励算法题和系统设计题讨论的决定：

我们：
1. 希望能看到干货讨论；
2. 希望能看到好的代码（web端高级发帖模式下，@ 朋友右边的<> 可以选择多种代码）

版主 @14417335 负责审核加分，也请大家给好的回复加分 + 顶。
大家给30，我会跟进奖励30，double之；
大家给100，我也会跟进奖励100，double之。

很理解大家写代码、调试、写思路分析，很花时间。对于特别好的回复，还会有额外加分。

欢迎大家拿出好的题目讨论，选中了我会全站置顶。哪位同学起了好的题目/帖子，激发了干货讨论，也会获得一定的积分奖励。

欢迎大家踊跃参与。看到好的回复，也请大家顶一下，作为对别人积极参与讨论、热心分享的认可和鼓励。
其他可以获得双倍积分的题目：

在刷题版里选择高频题标签，链接:
https://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=84&filter=typeid&typeid=1019

大家看到LC没有的高频题，也请贴到刷题版里，又有大米又有赞。对于学弟学妹们也是功劳一件。举手之劳。谢谢大家的参与。

umialpha 发表于 2019-4-3 11:51
网上大多数方法应该还是用dfs，如果面试官不介意的话，可以用dfs找出所有的cycle取最短的那条。时间复杂度 ...

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