我考虑过标记我访问过的所有节点。当我发现一些设置了标志的节点时，它是循环的。但这不起作用，因为一个节点可以有多个父母和多个孩子。我怎样才能找到循环？
PS：我知道寻找循环更适合DFS，但我需要通过BFS来做。
问问题
1650 次
2 回答
0
找出直接图是否包含环与确定图是否具有拓扑排序/顺序是相同的问题。也就是说，找出图形的所有顶点是否可以以线性方式排列，其中任何一个顶点的所有出站边总是指向其右侧更远的另一个顶点。
这个概念是这样的；具有拓扑排序的图，也称为有向无环图 (DAG)，将始终具有至少一个没有任何入界边的顶点。你可以很容易地通过矛盾来证明这个陈述：如果每个顶点都有一条入界边，那么在图中向后走最终会导致在一次遍历中访问一个顶点两次，这意味着它有一个循环，并且它不是 DAG。
从 DAG 中删除顶点及其出界边永远不会导致创建新循环。在拓扑顺序的线性视觉表示中，最左边的顶点没有入界边。如果要以拓扑顺序一个接一个地删除最左边的顶点及其边，他们将始终删除没有入界边的顶点，因为它们要么开始时没有任何边，要么其入界边被其他人删除被移除的顶点。只有没有任何入界边或出界边的顶点会在被移除之前保留下来。
如果顺序删除没有入界边的每个顶点并没有清除图中的每个顶点，这意味着图中存在一个循环并且它不是 DAG。
按照这个想法，您可以使用 FIFO 数据结构来支持 BFS 的算法将是首先确定所有顶点上的入站边数。您可以通过在开始时执行 BFS 来实现此目的，并且对于发现的每个出站边缘，在其主邻接列表节点中增加相应邻居的入站边缘计数器。
在算法的核心部分，您需要搜索顶点并将当前没有入站边的顶点添加到队列中。添加所有当前可用的后，从队列的前面开始检查顶点。通过遍历其邻居并将每个相应的入站边计数减 1 并将其从图中删除，并检查新计数是否已达到零。如果是，则将该顶点添加到队列中。完成递减后，移动到队列中的下一个顶点。对队列上的所有顶点继续相同的过程。这个过程看起来像多个 BFS，源自没有入界边的每个顶点。
最后，如果移除的顶点数与总顶点数相同，则该图是一个 DAG，不包含环。如果不是，这意味着剩余的顶点是一个/多个循环的一部分。
虽然这个问题很老了，但我祝你好运！
于 2019-09-12T06:18:48.643 回答
0
上面的答案是正确的，但我认为它不是 BFS，或者至少不是直观的 BFS。主要是检查每个节点的出边，删除与没有入边的节点相连的边。我的回答可能是对这个问题更直观的 BFS 实现。
让我们想想什么是循环？
一个节点可以找到一条到达自己的路径，那么就有一个循环。
那为什么 DFS 可以解决查找循环任务而 BFS 不能呢？
为了在有向图中找到环，我们首先提出了 DFS：如果 DFS 树中有后边，那么图中就有环。在构建 DFS 树时，我们可以记录每个节点的起始计数器和结束计数器，以便我们可以检查指向节点是否是当前节点的祖先。一旦找到后边缘（指向节点尚未完成，而是在当前节点之前开始），这意味着该节点可以找到返回其祖先之一的方法。而 BFS 用于充分探索邻居但无法拯救祖先。所以，如果在遍历图表时保存祖先，也许我们可以让 BFS 解决这个问题：
在 BFS 期间，当每个节点探索其邻居（或子节点）时，会将累积的祖先信息发送给其邻居。当一个节点发现从他的父节点传来的一个祖先是他自己时，那么图中就有一个循环。这是一张图片显示了这个算法的步骤：
步骤 1，A 探索他的邻居：B、C、D、E，并将祖先信息 {A} 发送给他们。
步骤 2，B 探索他的邻居 E 并将祖先信息 {A, B} 发送给它。
第 3 步，C 探索他的邻居 D、F 并向他们发送祖先信息 {A,C}。
第 4 步，D 没有找到邻居。
第 5 步，F 探索他的邻居 D、G 并向他们发送祖先信息 {A、C、F}。
第 6 步，G 探索他的邻居 C 并向其发送祖先信息 {A, C, F, G}。然后C会发现他的祖先就是他自己，那么就会有一个循环。
那么，这个算法的运行时间呢？传统 BFS 的运行时间是 Theta(V+E)，但在该算法中，祖先信息的传递和联合，总共需要 E 步，而每一步信息数组的大小比 C*V 大 1 小。所以总运行时间是O(EV)，Omega(V+E)。
于 2020-02-19T20:00:30.667 回答