广度优先搜索 (BFS)

把石子丢进池塘,涟漪会一圈一圈均匀地散开。广度优先搜索也这样探索图:先是离起点一步的所有节点,再是两步的,依此类推。正是这个简单的顺序让它能找到最短路径。

一张由字母节点组成的图,节点按到起点的距离分圈着色,下方画着节点队列
一张由字母节点组成的图,节点按到起点的距离分圈着色,下方画着节点队列

基本思想

图是一组由边连接的节点:地点和道路、人和友谊、迷宫的格子和格子之间的通道。广度优先搜索回答的问题是:从这里出发,能到达哪里,最少要几步?它维护一个待访问节点的队列。从队首取节点、把新节点加到队尾,意味着节点按被发现的顺序处理。

逐步讲解

把起点放入队列,距离为 0。取出队首的节点。对每个尚未见过的邻居,把它的距离记为当前节点的距离加 1,记下当前节点作为到达它的来路,并把它加入队尾。跳过之前见过的邻居。重复,直到队列为空或到达终点。

一个例子

设一张图有边 A–B、A–C、B–D、C–D、C–E 和 D–F,从 A 开始。从队列取出 A,找到距离为 1 的 B 和 C。取出 B,找到距离为 2 的 D。取出 C,发现 D 已经见过,并找到距离为 2 的 E。取出 D,找到距离为 3 的 F。E 和 F 没有发现新节点,队列为空。从 F 沿记下的节点往回走得到 F ← D ← B ← A,所以从 A 到 F 的一条最短路径是 A → B → D → F,长三条边。

为什么距离是对的

距离为 1 的每个节点都先于距离为 2 的任何节点入队,距离为 2 的又先于距离为 3 的,依此类推,因为一个节点的邻居只有在它自己出队时才会入队。所以第一条到达某节点的路径边数最少,BFS 从不需要修正距离。每个节点只取出一次,每条边从两端各看一次,所以工作量随节点数加边数增长。

历史与应用

Konrad Zuse 在 1945 年关于 Plankalkül 语言的研究中描述了广度优先搜索,但这项研究直到 1972 年才发表。Edward F. Moore 在 1959 年重新发明了它,用来找走出迷宫的最短路径;C. Y. Lee 在 1961 年用它在电路板上布线。如今,它用来求谜题的最少步数、社交网络中的分隔度数、网络爬虫最先抓取的页面,以及游戏中最近的空格子。当边有长度时,Dijkstra 算法是它的推广。

康拉德·楚泽(中,戴眼镜)与海因茨·比林(左)在慕尼黑SYSTEMS ’91展览会上。楚泽于1945年在其Plankalkül语言的工作中描述了广度优先搜索,该工作直到1972年才发表。
康拉德·楚泽(中,戴眼镜)与海因茨·比林(左)在慕尼黑SYSTEMS ’91展览会上。楚泽于1945年在其Plankalkül语言的工作中描述了广度优先搜索,该工作直到1972年才发表。

动手试试

打开应用并按“单步”。正在访问的节点会高亮,在队列中等待的节点为蓝色,已访问的节点为绿色,并各自标有距离。队列显示在图下方,队首在前。把点击切换为“终点”并选一个节点,可以在那里停下并查看最短路径;也可以生成一张节点和边更多的新图。

常见问题

BFS 的时间复杂度是多少?

O(V + E),V 是节点(顶点)数,E 是边数:每个节点入队和出队各一次,每条边从两端各检查一次。它需要 O(V) 的额外内存来存放队列和距离。

BFS 为什么用队列?

因为先进先出让节点保持被发现的顺序,也就是距离从小到大的顺序。如果改用栈,搜索会先往深处走:那就是深度优先搜索。

BFS 能在带权图中找最短路径吗?

一般不能:它计的是边数,而不是边的长度。对于没有负权边的带权图,请使用 Dijkstra 算法。如果每条边的权重都是 0 或 1,可以用一种叫 0-1 BFS 的变体。

BFS 用在哪里?

用最少步数解谜题和走迷宫,在社交网络中找朋友的朋友,逐层抓取网页,在网络中广播,还作为其他算法的基础,例如求最大流。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

试试广度优先搜索