graph-algorithm - BFS循环检测

Question

有人可以提供一步一步的伪代码，使用 BFS 在有向/无向图中搜索循环吗？

它可以得到 O(|V|+|E|) 复杂度吗？

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

Answer 1

您可以采用非递归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 它的循环块用于循环检测，并删除了原始的如果达到目标块以进行目标检测。总的来说，它是相同的算法。

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

有关周期和 BFS 的更多信息，请阅读此链接https://stackoverflow.com/a/4464388/6782134