查询s到w路径放到vector那个函数有不明白的地方

Question

int p = w;    
while( p != -1 ){    
s.push(p);    
p = from[p];    
}

这里的p是from数组的索引值么，还是w点本身的值？如果是本身的值，那么带到from里就变成索引了，应该是无法按顺序提取w以及之前的点的值的，还有这个p = from[p];   也不太明白为什么可以表示是w前一个点。

Answer 1

liuyubobobo 2017-07-06 07:05:26

from[x]表示的就是节点x之前的节点是谁。

我们的p从w开始即从终点开始每次先将自己记录下来保存在s中之后通过p = from[p]寻找当前节点的前一个节点是谁再做记录保存在s中... 依次循环。

依然是可以使用一个小数据量试验一下代码在这个代码片段中一步一步跟踪看p是如何变化的s中存储了什么为什么最终获得了整条路径代码运行的哪一部分和自己的设想不一样。这是非常重要的学习编程的方式。

P.S. 课程中给的测试用例所使用的图就足够小。只有7个节点8条边。

加油

• mahsiaoko #1

  老师，这个地方为什么要把w赋值给p，不可以直接使用w吗

• liuyubobobo 回复 mahsiaoko #2

  可以！：）

• mahsiaoko 回复 liuyubobobo #3

  谢谢老师！