java - 使用 BFS 在有向图中查找循环？

Question

我考虑过标记我访问过的所有节点。当我发现某个节点设置了标志时，它就循环了。但这是行不通的，因为一个节点可以有多个父节点和多个子节点。我怎样才能找到循环？

PS:我知道DFS更适合寻找循环，但我需要通过BFS来完成。

Answer 1

判断一个有向图是否包含环与判断该图是否具有拓扑排序是同一个问题。也就是说，找出图的所有顶点是否可以以线性方式排列，其中任何一个顶点的所有出站边始终指向其右侧的另一个顶点。

概念是这样的；具有拓扑排序的图，又称有向无环图 (DAG)，将始终具有至少一个没有任何入界边的顶点。您可以轻松地通过反证法证明这一说法:如果每个顶点都有入界边，则向后遍历图最终将导致一次遍历访问一个顶点两次，这意味着它有一个循环，并且它不是 DAG。

从 DAG 中删除顶点及其出界边绝不会导致创建新的循环。在拓扑顺序的线性视觉表示中，最左边的顶点没有入界边。如果要按拓扑顺序一一删除最左边的顶点及其边，那么它们总是会删除没有入界边的顶点，因为它们要么一开始就没有任何入界边，要么其入界边被其他顶点删除了。被移除的顶点。在被删除之前，只有没有任何入站边或出站边的顶点才会保留。

如果依次删除没有入界边的每个顶点并没有清除图中的每个顶点，则意味着图中存在循环，并且它不是 DAG。

<小时/>

按照这个想法，可以与 FIFO 数据结构一起使用来支持 BFS 的算法是首先确定所有顶点上的入界边的数量。您可以通过在开始时执行 BFS 来实现此目的，并且对于发现的每个出站边缘，增加其主邻接列表节点中相应邻居的入站边缘计数器。

在算法的核心部分，您需要搜索顶点并将当前没有入站边的顶点添加到队列中。添加所有当前可用的顶点后，从队列的前面开始检查顶点。通过遍历其邻居并将每个相应的入界边计数递减 1，并检查新计数是否已达到零，将其从图中删除。如果是，则将该顶点添加到队列中。完成递减后，移动到队列中的下一个顶点。对队列中的所有顶点继续执行相同的过程。这个过程看起来像是源自每个没有入界边的顶点的多个 BFS。

最后，如果移除的顶点数与顶点总数相同，则该图是 DAG 并且不包含环。如果不是，则意味着剩余的顶点是一个/多个循环的一部分。

虽然这个问题已经很老了，但我祝你好运!