如何检查边缘是否处于某个周期？

Question

我有一个问题,要求一个算法检测任何包含任何给定边'E'的无向图中是否有任何循环.该算法应在O(N)线性时间内运行.

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

任何提示？

Answer 1

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

Answer 2

您从边缘“e”开始。从它你应该得到它连接的两个顶点。从它们中，您可以获得其他边和其他顶点，以及其他边和其他顶点，并且...您需要一种方法来确定顶点是否已被您的算法“访问”。如果有，则存在“e”所属的循环。