如何检测无向图是否具有循环并使用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
}

在调用dfs(r, nil)某个顶点r（和任何非顶点值nil）之后，cycleVertices如果找到了一个循环，将填充一个循环。

[编辑：正如胡安洛佩斯所指出的，取消标记顶点是没有必要的，并且可能会造成混淆；但是，有趣的是，不会影响无向图的时间复杂度。]

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

到最后，cycle 将包含图中找到的循环，否则它将为空。另请注意，循环的显示顺序取决于您如何“推”到循环（推到后面将向后打印，推到前面将“按顺序”打印）

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