使用BFS检测周期

Question

我知道这是一个常见的问题。但在许多地方，我读到使用BFS的循环检测对于有向图是不可能的。一个例子是这个链接Why DFS and not BFS for finding cycle in graphs

我认为我们可以使用BFS实现有向图的拓扑排序。如果存在拓扑序，则我们可以说图是无圈的，否则它是循环的。这不可能吗？

Answer 1

可以使用广度优先算法方法检测图中的循环，通过队列处理值。当你访问一个顶点V时，如果任何连接到V的顶点U已经被访问过并且不是V的父节点，那么图中就存在一个循环。否则，该图将没有循环。这种方法是基于图中没有平行边的假设。

Answer 2

可以使用BFS检测周期！您甚至可以检测到图的最短循环。

节点数等于n。从每个节点运行bfs。伪码：

1 create a queue Q
2 create a array visited
3 create a array level
4 set answer = infinity
5 for each node 1 to **n**
6      mark the visited equals to **0**.  
7      clear the **Q**
8      enqueue **v** onto Q
9      visited [ v ] = 1
10     while Q is not empty:
11            t <- Q.dequeue()
12            for all edges e in G.adjacentEdges(t) do
13            u <- G.adjacentVertex(t,e)          
14            if u is not visited:
15                 visited [ u ] = 1
16                 level [ u ] = level [ t ] + 1;
17                 enqueue u onto Q
18            else:
19                 answer = min( answer , level [ t ] + level [ u ] + 1 )

完成算法后，您将得到整个图中的最小圈作为答案。