在图上走的两种方法

从一个点出发

上次看了图。
点是节点，线是边，
没有环的图就是树。
这次在上面走走。
要走，先
定从哪儿出发。
选一个点，
直接连着的邻居就出来了。

点一个点定出发点。(出发点 = 蓝 · 直接连着的邻居 = 亮起)

从出发点走一步
到邻居。
从那儿再走一步
就是邻居的邻居。
就这么沿着线
挪脚，
一个个踩点，
就是在图上走。

近的先来，广度优先

第一种走法是水波。
先踩出发点紧挨着的，
再往外一层，
再一层。
像往池塘扔石头
圈圈散开，
从近到远依次
往外铺。

每次点击就像水波一样散开一层。(踩到的点 = 上色 · 同一层就是同样的距离)

水波散开的时候，
还没去到的点
排在等候的队里。
先排队的点
就先依次去拜访。
所以近的点
总在远的点前面。
层就是距离。

走到头，深度优先

第二种走法是走迷宫。
挑一条路
能走多远走多远。
没地方可去了
就退一步
再钻没走过的岔路。
不往宽里散，
而是往深里钻。

点击沿一条路走到头，走不通就退回来。(当前点 = 蓝 · 退回的路 = 变暗)

为了别忘了回来，
把走过的点堆起来。
从堆好的那堆里
从最上面一个往回找
找岔路。
所以深度优先
先回到
最近去过的地方。

广度优先给出最短

水波不是白散开的。
因为先踩近的层，
第一次到达某个点的那一刻
就是到它最快的路。
如果每条线距离都一样，
在第几层到达
就是离出发点的距离。
没有绕路。

点击比较两种走法的到达顺序。(广度优先的层号 = 就是最短距离)

深度优先快又远，
但可能绕着到。
所以最短距离
归水波，也就是广度优先。
不过现在我们把每条线
都当成一样的距离。
要是线的距离不同
那又是另一回事，留到下次。

小结

我们看了在图上走的两种方法。
广度优先像水波
从近处一层层散开，
深度优先沿一条路
走到头再退回来。
两种都踩到每个点，
只是顺序不同。
距离相同时广度优先最短。

点开这两种走法。(广度优先 = 水波 · 深度优先 = 走到头)

在地图上找路，
顺着朋友的朋友走，
走出迷宫。
在图上走
比想的离我们更近。
下次聊在线的距离不同的
图上，
找最快的路。