广度优先搜索及其应用

在入门教程中，你体验了一个角色在迷宫中移动以到达目标的游戏。一开始，需要寻找距离目标为0的方块。然后寻找距离目标一步之遥的所有方块。然后在寻找距离目标两步的所有方块。 然后距离三步的方块，依此类推，直到到达角色开始的方块。如果你从所来的距离为 $k$‍ 的方块，继续追踪下一个距离为 $k+1$‍ 的方块，就可以回溯找到从角色到目标的路线。

下图是我们在入门教程中所看到的情况：

现在可以将其判断为为无向图。每个顶点对应着不是墙的一部分的方块，并且每个边都入射在相邻的正方形上。

通过上述程序找到的路线具有重要的属性：没有其他从角色到目标的路线会经过更少的方格。那是因为我们使用了一种称为广度优先搜索的算法来找。 广度优先搜索 (Breadth-first search)，也称为BFS，根据路径中的边数，找到从给定源顶点到所有其他顶点的最短路径。

还有另一个广度优先搜索的例子："六度凯文贝肯"游戏。在游戏中，玩家根据在电影中与谁一起出现的链条，尝试将电影演员和演员连接到凯文贝肯。链条越短越好，并且令人惊讶的是，有多少演员能够以六条或更少的链条连接凯文贝肯。以澳大利亚女演员凯特贝尔为例。2006年，她和奈许·埃哲顿起出演 麦克白；埃哲顿于2003年与劳伦斯·菲什伯恩 一起参演了 黑客帝国重装上阵；而菲什伯恩在2003年与凯文贝肯一起出演了 神秘河流。 因此，凯特贝尔的"凯文贝肯数"是 3\ 。事实上，有几种方法可以发现凯特贝尔的凯文贝肯数是3。你可以在 Oracle of Bacon website 上查找任何演员的凯文贝肯号。

正如你可能已经发现的那样，Oracle of Bacon 网站维护着一个无向图，其中每个顶点对应一个演员，如果两个人出现在同一部电影中，那么它们的顶点就会出现边事件。 凯文·贝肯（Kevin Bacon）从顶点开始的广度优先搜索找到了所有其他演员的最短链。

本内容是 达特茅斯计算机科学 教授 Thomas Cormen 和 Devin Balkcom，与可汗学院的计算课程团队合作完成。内容获得许可 CC-BY-NC-SA。