BFS示例中最短路径查找、edgeTo存储与pathTo逻辑疑问解答

edgeTo不是二维数组，是普通的一维数组，核心作用是记录BFS遍历过程中每个节点的前驱节点：

• 数组索引对应图里的顶点编号
• 数组存储的值，是「第一次访问到该顶点时，是从哪个相邻顶点走过来的」，也就是最短路径上该顶点的上一个节点。

它的赋值逻辑完全嵌在BFS流程里：当你从队列取出当前节点v，遍历v的所有邻接节点w时，如果w还没被标记访问过，就说明我们是第一次到达w，这条路径就是从源点到w的最短路径，直接执行this.edgeTo[w] = v，把w的前驱记为v，再标记w入队即可。BFS层序遍历的特性保证了每个节点第一次被访问时的路径长度一定最短，所以不需要后续再更新edgeTo的值。

你觉得陌生的for循环，本质是从目标节点逆着前驱指针往源点回溯，一步步拼出完整路径，我们把这个循环拆开看：

for (var i = v; i != source; i = this.edgeTo[i]) {
    path.push(i);
}

三个逻辑块分别对应：

1. 循环起点：var i = v，从你要查询路径的目标顶点v开始回溯
2. 终止条件：i != source，只要还没回溯到源点（你代码里源点固定为0），就继续循环
3. 步进规则：i = this.edgeTo[i]，每一轮都把当前节点替换成它的前驱节点，往源点方向走一步

举个直观的例子：假设源点是0，遍历后edgeTo的记录为edgeTo[1]=0、edgeTo[2]=1、edgeTo[4]=2，要查询0到4的路径时：

• 初始i=4，不等于0，把4存入path，i跳转到edgeTo[4]=2
• i=2，不等于0，把2存入path，i跳转到edgeTo[2]=1
• i=1，不等于0，把1存入path，i跳转到edgeTo[1]=0
• 此时i等于源点0，循环结束，最后把0存入path，得到的数组是[4,2,1,0]，反转后就是从源点到目标点的正向最短路径[0,1,2,4]

另外你贴的代码里有个小笔误：pathTo函数最后一行path.push(s)里的s没有在该函数作用域内定义，应该替换为前面声明的source，否则会报引用错误。

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