如何跟踪访问bfs / dfs中所有节点的路径

Question

这类似于How to trace the path in a Breadth-First Search?，但是该帖子答案中描述的方法似乎不适用于我的情况。

在这里，我的意思是指从开始到结束状态的一系列连接节点。

考虑一个顶点为V = {a，b，c}且边沿为{{a，b}，{a，c}}的无向图，并假设我们必须按字母顺序遍历后继。我们从节点a开始，结束状态是访问所有3个节点。

首先进行广度搜索将首先访问边缘a->b，然后访问边缘a->c。因此，求解路径为a->b->a->c。由于b和c之间没有边，因此我们必须返回a（因此我们必须遍历边b->a）。在以上链接文章的答案中，接受的解决方案将仅输出a->c。

我想不出一种修改传统bfs算法的方法。对于dfs，我也有同样的问题，但现在我想从bfs开始。

Answer 1

遍历序列和路径是两个不同的集合，不应混淆。遍历序列或访问的顶点是您在两个顶点之间搜索路径时访问的所有顶点。该路径仅包含将源连接到目标的那些链接的顶点（边）。考虑下图：

在搜索从0到3的路径时，假设您根据顶点的值选择顶点，则BFS遍历顺序为0,1,4,6,2,5,3。该搜索找到的路径是0->1->2->3

Answer 2

想这样做似乎很奇怪。深度优先搜索（DFS）肯定会更简单，它总是跟随一条边或沿着该边回溯。相反，广度优先搜索（BFS）通常不会访问（或回溯到）与先前访问的节点相邻的节点。

特别是，您的问题的这一部分是错误的，并显示出误解：

由于b和c之间没有边，我们必须返回a（所以我们必须遍历边b -> a）。

BFS在您的示例中永远不会从b到a遍历边。它完成了对b的访问，然后从队列中轮询c并立即访问c，而没有通过a进行“旅行”。

比喻，将DFS视为一条路径是很有意义的；如果您在迷宫中，则可以使用面包屑标记您“已访问”的地方，从而通过DFS解决迷宫。相反，人类无法通过BFS解决迷宫，因为人类无法“传送”到他们以前去过的地方。 BFS不会有意义地描绘出您可以沿着图形的边缘行进的路径。

---

就是说，如果您确实想要，您可以构造一条访问图的节点的路径，以使每个节点第一次的访问顺序与BFS相同。最简单的方法是执行BFS，以“ BFS顺序”构建节点列表，同时还构建“ BFS树”。然后，对于BFS顺序中的每个节点，您可以通过BFS树中它们的最低公共祖先从上一个节点到达它。此路径仅通过以BFS顺序先前已访问过的节点。