data-structures - 广度优先搜索用于搜索循环图中任意两个节点之间的所有路径

Question

我正在尝试使用 BFS 获取循环图中两个节点之间的所有路径。我发现 BFS 不会跟踪它之前的节点，所以需要添加一些其他的集合来实现相同的效果。

问题是 - 我们是否应该避免使用 BFS 来获取节点中的所有路径并使用 DFS 或 BFS 也可以提供潜在的解决方案。

如果它在那里，请为我提供相同的逻辑。

Answer 1

我假设您只想找到简单的路径（没有循环），否则可能会有无限的路径。如果这不是一个要求，那么理论上 BFS 或 DFS 都可以工作（尽管 DFS 只会继续探索一个循环，永远不会找到其他更短的路径），但取消这个要求并没有真正的意义。

对于 BFS 和 DFS，每个节点都应该有一个已处理的标志，以防止循环图中的无限多路径。

考虑以下：

A with children B, C
B with children C, D
C with children B, D

使用 BFS，您会错过 A -> C -> B -> D，因为 B 在处理 C 之前已被标记为已处理。

使用 DFS，这不会成为问题，因为在向上备份树时应重置已处理标志。

到目前为止，您可以跟踪每个节点的整个路径，但这不可行，因为它需要大量额外的存储空间和时间。

您可以摆脱 BFS 的已处理标志并在路径中的节点数 > 树中的节点数时停止处理，并从输出中删除所有非简单路径。