今天我就来谈一谈什么是广度优先搜索吧。
广度优先搜索，又名宽度优先搜索，英文 breadth-first search ，是最简单的图的搜索算法之一。
多言何益？不如一例：如果我要坐上海地铁，从松江新城到滴水湖玩，要求经过的站最少，我该怎么走？这就是一个要用到广度优先搜索的例子，见图：
温馨提示：写作时完整地铁图在这里，不一定最新（顺便吐槽一下，9号线三期东延伸段说是6月份就开，这都8月底了还不开……郁闷）。最新版在这里。
首先，我在松江新城站，也就是说，我到这个站的距离为0：
松江新城站只有9号线，那我们就沿着九号线继续走。
问题来了，往北（杨高中路方向）走，还是往南（松江南站方向）走？
你可能一眼就看出来了，并且有许多理由拒绝往南走，但是电脑，以及你写的程序并不会一眼就看出来啊。
不过你可以“分身”，命令一个人往北，一个人往南，毕竟你又不是真的在走。
这时，他们分别到了松江体育中心和松江大学城。这两站到距离为1，就简称距离1吧。
以此类推，他们又走了两步。
哎呀！往南走的没路走了，好吧，只能停下来了。 往北继续走，并且拐了个弯，往东，然后到了宜山路站。
新情况！宜山路站可以换乘黄色的3号线和蓝紫色的4号线。像之前决定往南走还是往北走的时候一样，派四个人走3/4号线，两个方向都要哦。
同样，换乘红色的1号线，浅紫色的10号线，咖啡色的11号线，也要派人走。
又是新情况！！！我们在距离11时，派了一个人走4号线，往东南，他在距离12，上海体育馆时派了一个人走1号线，往东北，到徐家汇站。同时，一直走9号线往东的人在距离12时已经到了徐家汇站。那我们就忽略距离长的，让我们的图不要太乱。
让我们继续前进。一边走，一边想：广度优先搜索的名字也是有道理的。“搜索”，表明它搜索了一个路径；“广度优先”，说明它优先走得多。另外，我们走的步数有一个好听的名字：时间戳。
很久很久以后，我们得出了终极答案：在距离33的时候，9号线徐家汇换11号线罗山路换16号线最终到达滴水湖。
我们还可以继续走下去。然后我们可以建立一个索引，以后我要知道从松江新城出发怎么走战术最少，看一下图就知道了。
人用这个算法处理这个问题确实是比较慢，不过电脑就不会这样慢了。我们要做的，就是写一个程序，然后让它执行这个步骤。（等我写好了我就贴在这里）。正常人的话，还是不要用这种算法了，免得约定时间到了你还在推算呢。
但是，这有一个问题。比如，我们要到2号线西边终点站徐泾东，按照之前的算法，路线是9号线宜山路换3/4号线，虹桥路换10号线，虹桥火车站换2号线。但是，这样要换4次车，一般人会不开心啊。解决办法之一就是，如果已经换成了3次，那么只沿着这条线一直走下去而不换乘。这样，之前这条路线就会到达上海火车站，而另外一条（9号线宜山路换3/4号线，中山公园换2号线）就会最终到达徐泾东。
还有一个问题，比如有一条快捷线，只有三站，松江新城-世纪大道-徐泾东，这明显绕了一个大圈，但是只用坐2站就可以到了。或者这也许不现实，现实一点的例子是，11号线站距长，8号线站距短，可能8号线比11号线还要快很多，这对于我们的要求“站最少”来说，确实是最少的，但是人会吃不消啊。那我们改变一下要求，“时间最少”，那该怎么办？还能用广度优先搜索吗？
其实可以的，我们只需要知道站与站之间要走几分钟，换乘需要几分钟，可以有0.5，然后从起点，半分钟半分钟走（当然你也可以把时间设定为整数，然后1分钟1分钟走，不过精度就会差一些）。这其实也是广度优先搜索。
那么，走迷宫也可以用广度优先搜索吗？
当然可以，但是，相率很低。毕竟你不可能在走迷宫之前有它的地图。如果有，确实可以。走迷宫最好用深度优先搜索，下次再介绍吧。
最后，提一句不相关的，如果你觉得上海地铁复杂到要疯掉，那么你绝对没看过东京地铁图，我把它贴在这里了。
