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

来源：7-6 寻路

envy

2017-07-05

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

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

写回答

1回答

liuyubobobo

2017-07-06

已采纳

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

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

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

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

加油

mahsiaoko

liuyubobobo

谢谢老师！

2020-03-09

共3条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

回答 1

回答 2

回答 5

回答 1

回答 3