如何检测无向图是否有循环并用BFS或DFS输出

Question

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

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

Answer 1

要用DFS检测和输出一个循环，只需在到达时标记每个顶点；如果标记了当前顶点的任何子节点，那么您就知道您有一个涉及该子节点的循环。此外，您知道该子顶点是DFS遇到的属于这个特定循环的第一个顶点，并且DFS中自第一次遇到该顶点以来的每一次移动（即，从那以后尚未返回的每一次递归调用）都访问了循环中的另一个顶点。唯一需要向调用堆栈中传递的信息是这个子顶点，或者指示未找到循环的特殊值。您可以将其作为返回值传回：

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]:
                Append v to cycleVertices
                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
}

对某个顶点r调用DFS(r,nil)（以及任何非顶点值nil)后，如果找到循环，则将用循环填充CycleVertices。

[编辑：正如Juan Lopes所指出的，没有标记顶点是不必要的，而且可能会使人困惑；但有趣的是，这并不影响无向图的时间复杂度。]