BFS 循环检测

Question

有人可以提供使用 BFS 在 directed/undirected 图中搜索循环的逐步伪代码吗？

它能达到 O(|V|+|E|) 复杂度吗？

到目前为止我只看到了 DFS 实现。

Answer 1

您可以采用 non-recursive DFS 算法来检测无向图中的循环，其中您将节点的堆栈替换为队列以获得 BFS 算法。很简单：

q <- new queue // for DFS you use just a stack
append the start node of n in q
while q is not empty do
    n <- remove first element of q
    if n is visited
        output 'Hurray, I found a cycle'
    mark n as visited
    for each edge (n, m) in E do
        append m to q

由于 BFS 仅访问每个节点和每个边缘一次，因此复杂度为 O(|V|+|E|)。

Answer 2

我发现 BFS 算法非常适合。时间复杂度相同。

你想要这样的东西（从维基百科编辑）：

Cycle-With-Breadth-First-Search(Graph g, Vertex root):

    create empty set S
    create empty queue Q      

    root.parent = null
    Q.enqueueEdges(root)                      

    while Q is not empty:

        current = Q.dequeue()

        for each node n that is adjacent to current:
            if n is not in S:
                add n to S
                n.parent = current
                Q.enqueue(n)
            else  //We found a cycle
                n.parent = current
                return n and current

我只添加了用于循环检测的 else 循环块，并删除了用于目标检测的原始 if reached target 块。总的来说，它是相同的算法。

要找到确切的周期，您必须找到 n 和 current 的共同祖先。最低的一个在 O(n) 时间内可用。比周期已知。 n 和当前的祖先。 current和n相连。

有关循环和 BFS 的更多信息，请阅读此 link

BFS 循环检测

BFS cycle detection

graph-algorithm

pseudocode

breadth-first-search

cycle-detection