这类似于如何在广度优先搜索中追踪路径？，但该帖子中答案中描述的方法似乎不适用于我的情况。
这里的路径，我本质上是指从开始到结束状态的连接节点序列。
考虑一个顶点 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 开始。
想要这样做似乎很奇怪。使用深度优先搜索 (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 顺序访问过的节点。