如何检测如果一个无向图有一个周期和输出使用BFS或DFS它

问题描述

在此另一个问题只是回答如何检测一个周期，而不是​​还输出它。所以，我想写O型算法运行BFS或DFS（V + E）时（V =顶点，E =边），在无向图，输出循环，如果它有一个。

The other question on this only answered how to detect a cycle, not also output it. So, I'd like to write an algorithm run BFS or DFS in O(V + E) time (V=vertices, E=edges), on an undirected graph, and output the cycle if it has one.

我所知道的，到目前为止是BFS / DFS是如何工作的，以及是否可以检测到循环使用BFS，如果你访问已经被标记为已访问节点。

What I know so far is how BFS/DFS works and that you can detect a cycle using BFS if you visit a node that already has been marked as visited.

推荐答案

要检测并输出与DFS一个周期，只是标记每个顶点，你得面对它。如果当前顶点的任何儿童被标记，你知道你有涉及这个孩子一个周期。此外，你知道，那个孩子顶点属于该由DFS遇到这一特定周期的第一个顶点，而在DFS的一举一动，因为它第一次遇到顶点（此后一直没有恢复，IE浏览器每次递归调用）先后走访了周期中的另一顶点。你需要传递回调用堆栈的唯一信息是这个孩子的顶点，或者一个特殊的值，表示无周期被发现。您可以通过这回作为返回值：

To detect and output a cycle with DFS, just mark each vertex as you get to it; if any child of the current vertex is marked, you know you have a cycle involving that child. Furthermore you know that that child vertex is the first vertex belonging to this particular cycle that was encountered by the DFS, and that every move in the DFS since it first encountered that vertex (i.e. every recursive call since then that hasn't yet returned) has visited another vertex in the cycle. The only information you need to pass back up the call stack is this child vertex, or a special value indicating that no cycle was found. You can pass this back as a return value:

dfs(v, p) {
    marked[v] = true
    For each neighbour u of v:
        If u != p:   # I.e. we ignore the edge from our parent p
            If marked[u]:
                Return u   # Cycle!
            Else:
                result = dfs(u, v)
                If result == FINISHED:
                    # Some descendant found a cycle; now we're just exiting
                    Return FINISHED
                Else if result != NOCYCLE:
                    # We are in a cycle whose "top" vertex is result.
                    Append v to cycleVertices
                    If result == v:
                        return FINISHED   # This was the "top" cycle vertex
                    Else:
                        return result     # Pass back up

    marked[v] = false    # Not necessary, but (oddly?) not harmful either ;)
    Return NOCYCLE
}

调用后 DFS（R，无）一段顶点研究（及任何非顶点值零）， cycleVertices 将填充一个周期如果被发现了。

After calling dfs(r, nil) for some vertex r (and any non-vertex value nil), cycleVertices will be populated with a cycle if one was found.

这篇关于如何检测如果一个无向图有一个周期和输出使用BFS或DFS它的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！