我有一个硬件问题，它要求一种算法来检测包含任何给定边“E”的任何无向图中是否存在任何循环。该算法应该在 O(N) 线性时间内运行。
我的问题是我不知道从哪里开始。我有一些简单的示例图，但我不知道从哪里开始。
任何提示？
最佳答案
从 G 中取出边 (u,v)。
1. 运行 BFS 以查看是否仍然可以从 u 访问 v。
2. 如果是，那么原始图有一个包含 e 的圈。否则没有。
关于graph - 如何检查边缘是否在某个循环中？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7733705/