如何检测无向图是否有周期并使用 BFS 或 DFS 输出它

Question

关于

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

到目前为止，我所知道的是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（以及任何非顶点值nil）调用dfs(r, nil)后，如果找到一个循环，cycleVertices将被填充一个循环。

[编辑：正如胡安·洛佩斯（Juan Lopes）所指出的，取消标记顶点是不必要的，并且可能会令人困惑;但是，有趣的是，它不会影响无向图的时间复杂度。

Answer 2

如果您使用的是 DFS，则可以根据是否已访问访问的节点以递归方式打印出节点的名称：

define function DFSVisit(node, cycle):
    if node.visited is true:
        push node.name to cycle
        return true
    else 
        set node.visited to true
    for each child of node:
        if DFSVisit(child, cycle) is true:
            set foundCycle to true
            break out of for loop
    if foundCycle is true:
        if (cycle.length <= 1 or cycle[first] != cycle[last]):
            push node.name to cycle
        return true
    else 
        return false

在它结束时，循环将包含在图形中找到的循环，否则它将为空。 另请注意，循环的显示顺序将取决于您如何"推动"循环（推到后面将向后打印，推到前面将"按顺序"打印）

编辑：非常感谢@j_random_hacker帮助我调试伪代码！