图搜索（graph search）运行过程中如何返回对应的有效路径？

首先你混淆了两种用途的图搜索：纯遍历用的无状态图搜索，和面向路径查找实现的图搜索。我们日常说「XX图搜索返回路径」时，默认指的是后者，所有面向路径查找的图搜索都会额外维护两个核心数据：

• 前驱映射表：记录每个节点是通过哪个相邻节点遍历到的
• （加权图必填）最小代价表：记录从起点到每个节点的已知最小移动代价

只要有这两个结构，不管遍历逻辑是什么，当终点被标记为已确认访问后，我们只需要从终点出发，沿着前驱映射表一直回溯到起点，把回溯的节点顺序倒过来，就是从起点到终点的完整路径。

无权重BFS的路径规则 #

无权重图的BFS有一个核心特性：节点第一次被访问（入队）时，对应的路径就是起点到该节点的最短路径，所以路径选择规则非常明确：

1. 你举的第一个菱形图例子，Start-B-Destination和Start-C-B-Destination两种访问顺序的差异，本质是代码里遍历Start的邻居时，先处理B还是先处理C的顺序问题，两条路径都是合法的最短路径，具体返回哪条取决于邻居遍历顺序，没有对错之分。
2. 第二个带D节点的图例子中，D是Start的直接邻居，Destination第一次被访问时的前驱是D，所以返回的最短路径就是Start-D-Destination，比走B/C的路径长度更短，是无权重场景下的最优解。

加权图/A*的路径规则 #

你提到的「首次访问节点的路径不是最短路径」的问题，标准的加权图搜索（包括Dijkstra、A*）已经做了对应处理，核心逻辑是：

1. 同一个节点可以多次加入边缘集（fringe），只要这次入队对应的路径代价比当前记录的该节点最小代价更低
2. 只有当节点从边缘集被弹出时，才确认它对应的当前代价是全局最小的，才会把它加入已访问集合（closed set）

就拿你举的A*例子来看：

• 第一次通过B访问到D时，记录的D的最小代价是3，前驱为B，把D加入边缘集
• 后续处理C节点时，发现通过C到D的代价只有2，比已记录的3更小，此时会更新D的最小代价为2，前驱改为C，再把D重新加入边缘集
• 边缘集排序后，代价更低的D条目会被优先弹出，此时D的前驱已经更新为C，最终回溯得到的路径就是代价更低的Start-C-D-Destination，而不是首次访问D时的路径。

如果启发函数满足可采纳性（不会高估剩余代价），A*算法最终返回的路径一定是全局最优的最短路径，不存在歧义。

内容的提问来源于stack exchange，提问作者citrate