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

Question

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

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

Answer 1

要使用 DFS 检测和输出循环，只需标记每个顶点即可；如果标记了当前顶点的任何 child ，则您知道您有一个涉及该 child 的循环。此外，您知道该子顶点是 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(以及任何非顶点值 nil)调用 dfs(r, nil) 之后，cycleVertices 如果找到一个循环，将填充一个循环。

[编辑:正如 Juan Lopes 所指出的，取消标记顶点是不必要的，而且可能会造成混淆；但有趣的是，它不会影响无向图的时间复杂度。]