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

我只为循环检测添加了一个循环块，并删除了原始的目标块(如果达到目标块的话)以进行目标检测。总之，这是相同的算法。

要找到确切的周期，您必须为n和当前找到一个共同的祖先。最低的一个在O(n)时间内可用。而不是已知的循环。N和现在的祖先。电流和n是连接的。

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