基本思想
图是一组由边连接的节点:地点和道路、人和友谊、迷宫的格子和格子之间的通道。广度优先搜索回答的问题是:从这里出发,能到达哪里,最少要几步?它维护一个待访问节点的队列。从队首取节点、把新节点加到队尾,意味着节点按被发现的顺序处理。
逐步讲解
把起点放入队列,距离为 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 算法是它的推广。
动手试试
打开应用并按“单步”。正在访问的节点会高亮,在队列中等待的节点为蓝色,已访问的节点为绿色,并各自标有距离。队列显示在图下方,队首在前。把点击切换为“终点”并选一个节点,可以在那里停下并查看最短路径;也可以生成一张节点和边更多的新图。
常见问题
BFS 的时间复杂度是多少?
O(V + E),V 是节点(顶点)数,E 是边数:每个节点入队和出队各一次,每条边从两端各检查一次。它需要 O(V) 的额外内存来存放队列和距离。
BFS 为什么用队列?
因为先进先出让节点保持被发现的顺序,也就是距离从小到大的顺序。如果改用栈,搜索会先往深处走:那就是深度优先搜索。
BFS 能在带权图中找最短路径吗?
一般不能:它计的是边数,而不是边的长度。对于没有负权边的带权图,请使用 Dijkstra 算法。如果每条边的权重都是 0 或 1,可以用一种叫 0-1 BFS 的变体。
BFS 用在哪里?
用最少步数解谜题和走迷宫,在社交网络中找朋友的朋友,逐层抓取网页,在网络中广播,还作为其他算法的基础,例如求最大流。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
试试广度优先搜索