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|)。