如何检查边是否在某个周期中？
我有一个硬件问题，需要一种算法来检测包含任何给定边“E”的任何无向图中是否存在任何循环。该算法应在 O(N) 线性时间内运行。
我的问题是我不知道从哪里开始。我有一些简单的示例图，但我不知道从哪里开始。
有什么提示吗？
I have a hw problem that asks for an algorithm that detects if there is any cycle in any undirected graph that contains any given edge 'E'. The algorithm should run in O(N) linear time.
The problem I have is that I don't know where to start. I have some simple sample graphs but I dont know where to go from there.
Any hints?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
从 G 中取出边 (u,v)。
1. 运行 BFS 以查看 v 是否仍可从 u 访问。
2. 如果是，则原图存在包含e的环。否则就没有。
Take out that edge (u,v) from G.
1. Run BFS to see if v is still reachable from u.
2. if yes, then the original graph has a cycle containing e. otherwise there is not.
执行深度优先搜索，将节点添加到列表中，并在返回时将它们从列表中删除。
该列表代表您当前的遍历路径。
如果您遇到列表中已有的节点，则存在循环/周期。
Do a depth first search adding nodes to a list as you go, and removing them from the list as you return.
The list represents your current path of traversal.
If you come across a node that is already in your list, then there is a loop/cycle.
您从边缘“e”开始。从它你应该得到它连接的两个顶点。从它们中，您可以获得其他边和其他顶点，以及其他边和其他顶点，并且...您需要一种方法来确定顶点是否已被您的算法“访问”。如果有，则存在“e”所属的循环。
You start with the edge 'e'. From it you should get the two vertices it connects. From them you get other edges and other vertices, and other edges and other vertices, and... You'll need a way to figure out if a vertex has already been 'visited' by your algorithm. If it has then there's a cycle that 'e' is part of.
对于边缘 (u,v)：
1- 从 u 开始执行深度优先搜索，确定是否找到 v 并且沿到 v 的路径存在后边缘。
2- 如果找到 u，则从 v 执行深度优先搜索并且 u 存在后沿，则存在一个包含 u 和 v 的循环。
换句话说，
1-从 u 开始执行 DFS，检查是否存在后沿且 v 尚未完成。
2-从v开始执行DFS，检查后边缘是否存在并且u尚未完成
如果两个条件都为真，则edge(u,v)属于一个循环。
For the edge (u,v):
1- perform a depth first search starting from u, determine if v is found and a back edge exist along the path to v.
2- perform a depth first search from v, if u is found and back edge exist to u, then there's a cycle that includes both u and v.
In other words,
1- perform a DFS starting from u, check if back edge exist and v is not finished yet.
2- perform a DFS starting from v, check if back edge exist and u is not finished yet
if both conditions are true, then edge(u,v) belong to a cycle.
在 G 上运行 DFS 并执行以下操作。考虑第一次遍历边 e 的情况。
有两种情况：
算法。对于 DFS 中找到的每个后沿 (w, x)，检查 w 是否是 v 的后代并且 x 是
u的祖先。如果是这样，我们就找到了一个包含边 e 的环。
Run DFS on G and do the following. Consider the first time the edge e is traversed.
There are two cases:
algorithm. For every back-edge (w, x) found in DFS, check if w is a descendant of v and x is
an ancestor of u. If so, we have found a cycle including the edge e.