什么是 BFS 和 DFS

从一个点出发

上一课看过了图：点是节点，线是边，没有环的图就是树。
这次来在图上走一走。要走，先得定好从哪儿出发。
选好一个点，最先看到的就是和它直接相连的邻居。

点一个点，定为出发点。（出发点 = 蓝色 · 直接相连的邻居 = 亮起来）

从出发点走一步，就到了邻居；从那里再走一步，就是邻居的邻居。
像这样顺着线挪步，一个个地踩过点，就是在图上走。

由近及远：广度优先

第一种走法是水波。先把出发点旁边的都踩一遍，再往外一层，再往外一层。
就像往池塘里扔块石头，水圈一圈圈荡开，从近处依次向外扩散。

每点一次，就像水波一样向外扩一层。（踩过的点 = 上色 · 同一层距离相同）

水波扩散时，还没走到的点在等候的队伍里排着，先排进队的点先去。
所以近的点总是比远的点先到。层数就是距离。

走到底：深度优先

第二种走法是走迷宫。挑一条路，能走多远就走多远。
无路可走了，就退回一步，再沿着没走过的岔路一直走下去。
不是往宽处铺开，而是往深处钻。

每点一次，就沿一条路走到底，走不通就退回来。（当前的点 = 蓝色 · 退回的路 = 变淡）

为了记得该退回哪里，把走过的点堆起来。
从这堆的最上面开始往回找岔路。所以深度优先总是先回到最近去过的地方。

广度优先给出最短路

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

点一个点，就能比较两种走法的到达距离。（广度优先的层号 = 最短距离）

深度优先走得又快又远，却可能绕了远路才到。所以最短距离是水波，也就是广度优先的本事。
不过眼下我们假定每条线长度都一样。要是每条线长度不同，就是另一回事了，下一课再讲。

总结

我们看了在图上走的两种办法。广度优先像水波一样从近处一层层扩散，深度优先沿一条路走到底再退回来。
两种都会踩遍所有的点，只是顺序不同。距离都一样时，广度优先给出的就是最短路。

点两种走法，各自的样子就会显出来。（广度优先 = 水波 · 深度优先 = 走到底）

在地图上找路、顺着朋友的朋友找人、走出迷宫，在图上行走这件事，其实离我们很近。
下一课，我们来在每条线长度不同的图上，找出最快的路。