我们在日常生活中常常有这样的场景，打开地图，查询某个地方到某个地方怎么乘坐公交车？地图通过算法计算就会告诉我们从哪个站出发，乘坐哪一条线路，在哪里换乘，最终到达目的地？这些都是怎么实现的呢？今天我们来学习队列与广度优先搜索，来简单实现下这个功能。

队列

在此之前，我们讲了栈又讲了深度优先搜索，今天我们来讲一讲它的孪生兄弟，广度优先搜索。了解广度优先搜索之前，有一个我们必须掌握的数据结构，队列。

队列是一种常用的数据结构，相信大家都不陌生，我们平时各种排队的动作，例如排队看医生、排队上地铁，就是队列。队列的特点，就是先排队的人先出队，我们称之为FIFO（First in first out），也就是先进先出。通常，我们可以使用数组或者链表来实现一个队列。

队列的操作，每次都是从末尾进队，从队首出队，上述例子，我们先让数据1，数据2，数据3分别进队，然后再依次出队。相信大家之前就已经了解过队列，这里也不做重复的叙述，今天我们来了解队列在广度优先搜索算法中的应用。

广度优先搜索算法（BFS）

搜索，又称之穷举，即找出问题的所有状态。有人可能会问，穷举不就是For循环么？For循环只是穷举的一种方式，毕竟很多问题都无法使用For循环来直接解决。举个简单的例子，著名的华容道问题，就难以使用for循环表示出所有的状态。

广度优先搜索，只是搜索的一种常见的手段之一。广度优先搜索的核心思想，就是对于每个状态，都找到与它距离最近的状态，搜索到的结果会进入队列，以便后面重新进行搜索。我们常说，算法只是一种套路，那么广度优先搜索的模板是什么呢？

初始状态入队while (队列不为空){ 取出队首 拓展所有可达状态 将有用的状态入队}

如何理解广度优先搜索算法呢，我们讲一个简单的应用，在一个国家里，有着复杂的交通网络，在这里，不同的城市之间有一些有高铁线路，现在我们想知道，从1号城市出发，只坐高铁，可以到达哪些城市。下图为城市的高铁线路图。

如果我们运用广度优先算法，顺序会是这样的，我们从1号城市出发，会发现2，3号城市，将2号城市进队，然后将3号城市也进队，接着我们发现1号城市没有相连的城市了，我们再从队列中取出2号城市，然后发现把与2号城市相连的4，5号城市进队，然后从队列中取出3号城市，逐个扩展，最后能够遍历出整个地图。而剩下两个节点从始至终都没有入队，说明他们不可到达。

我们把搜索过程中，所有的状态以及状态的转移表示出来，称之为搜索树，上图为刚刚的高铁问题的搜索树。有了搜索树，树上的边表示搜索的顺序。广度优先搜索的搜索树会呈现出一层一层的分级，只有当前层已经搜索拓展完了，才会处理下一层，如何为什么会有这样的现象呢？结合队列的特性，可以思考思考。

现在让我们回到最开始的那个问题，如果如何查询一个站点到另外一个站点的公交线路呢？我们从起点站出发，可以拿到经过这个站点的所有公交线路，然后就可以查询出所有从这个站坐车可以到达的站点，把他们入队，再从队列中逐个取出来，继续拓展，直到找到目的站点为止。我们也注意到，我们有些地图还有一些步行换乘的，在这里我们也是简单的修改一下可到达的站点的算法而已，相信聪明的你已经知道怎么实现了。

今天的介绍我们就讲到这里，如果你有兴趣，欢迎关注我，除了分享算法相关的，最近主要会讲一些redis的原理与应用。近期还准备了一些AI相关的知识，整理后会和大家继续分享。大家的支持是我继续唠嗑的动力。如果大家有什么疑问，欢迎提问。（同名公众号：沙茶敏碎碎念）