如何检查边缘是否处于某个循环？

Question

我有一个hw问题，要求提供一种算法来检测任何包含任何给定边“E”的无向图中是否有任何循环。该算法应该以O（N）的线性时间运行。

我遇到的问题是我不知道从哪里开始。我有一些简单的示例图，但我不知道从哪里去。

任何提示？

Answer 1

你从边缘'e'开始。从它你应该得到它连接的两个顶点。从它们中可以得到其他边和其他顶点，以及其他边和其他顶点，以及...您需要一种方法来确定顶点是否已被您的算法“访问过”。如果它有一个'e'是其中一部分的周期。

Answer 2

进行深度优先搜索，随时添加节点到列表中，并在返回时从列表中删除它们。

该列表表示您当前的遍历路径。

如果你遇到一个已经在你的列表中的节点，那么就有一个循环/循环。

Answer 3

对于边（u，v）的：

1-执行从u开始的深度优先搜索，确定如果v是发现和后边缘沿所述路径到v存在

2-。执行从v的深度优先搜索，如果u是发现和后边缘存在于U，然后有一个周期，其包括既u和v。

换句话说，

1-执行DFS从u开始，检查后边缘是否存在，v尚未完成。

2-执行从v开始的DFS，检查后边缘是否存在并且u还没有完成 如果两个条件都为真，则边（u，v）属于一个循环。

Answer 4

取出G.的边缘（u，v） 1.运行BFS以查看v是否仍可从u到达。 2.如果是，那么原始图形有一个包含e的循环。否则没有。