algorithm - 返回无向图中一个循环的路径的算法

Question

我正在尝试构建一种算法，该算法返回构成无向图中的一个循环的路径节点（如果有的话）。到目前为止，我所做的是在图上执行 DFS，直到我到达一个未发现的边缘，导致一个发现的节点（那时我知道有一个循环）。但是我怎么知道是哪条路径形成了循环。如果我使用堆栈/队列来记录我的路径，这对我有什么帮助？假设我从一个不属于循环路径的节点开始，我以后怎么知道将其从堆栈/队列中取出？

任何建议将不胜感激。

Answer 1

当您执行DFS记录时，您访问每个节点时来自哪个节点。为新节点调用它parent。现在，当您到达一条(u, v)通向已访问节点的边时v，沿着父节点创建的路径向上走到u，或直到DFS（表示 this s）的源头。

您将始终达到两者之一。如果您到达s，则执行相同的 fromv并且您有您的循环 - 从路径u到s路径从s到v和新边缘。如果你v再次到达你有一个循环 - 从u到v和比新边缘的路径。