- 当前
- 队列中
- 已访问
- 路径
广度优先搜索 (BFS)
广度优先搜索按圈层探索图:先是与起点相邻的所有节点,再是相隔两条边的所有节点,依此类推。它靠一个先进先出的队列做到这一点。点击一个节点从它开始,也可以选一个终点,然后逐步执行搜索,看队列如何增减、每个节点如何得到距离,以及最短路径如何出现。 按“播放”观看搜索过程,或用“单步”和“后退”一步一步查看。拖动步骤滑块可跳到任意位置。点击节点可将其设为起点;把点击切换为“终点”,再点击另一个节点,即可查找到它的最短路径。每个节点上的数字是它到起点的距离,图下方的一行是队列。“新图”会生成另一张图;可选择节点数和边数。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 跳到开头和结尾。
它是如何运作的
- 点击一个节点设为起点。要查找路径,把点击切换为“终点”,再点击另一个节点。
- 按“播放”,或用“单步”和“后退”一步一步移动。拖动步骤滑块可跳到搜索中的任意位置。
- 观察图下方的队列和每个节点上的距离。“新图”会生成另一张图供你尝试。
广度优先搜索的原理
把起点放入队列,距离为 0。然后重复:取出队首的节点,查看它的每个邻居。尚未见过的邻居得到比所取节点大 1 的距离,记下所取节点作为到达它的来路,并加入队尾。之前见过的邻居跳过。队列为空时,所有能到达的节点都有了距离。
为什么能找到最短路径
队列按发现的顺序交出节点,而节点是一圈一圈被发现的:距离为 1 的节点全部先于距离为 2 的节点入队,依此类推。所以一个节点第一次被到达时,走的路径边数最少。从终点沿记下的节点回到起点,就得到这条路径。这里只计边数;如果边的长度不同,就需要 Dijkstra 算法。
常见问题
什么是广度优先搜索?
一种从起点出发探索图的方法:先访问它的所有邻居,再访问邻居的邻居,依此类推,一圈一圈向外。它用队列让节点保持被发现的顺序。
广度优先搜索能找到最短路径吗?
能,前提是每条边都一样长:BFS 第一次到达某个节点时,用的边数最少。如果边的长度不同,请改用 Dijkstra 算法。
BFS 和 DFS 有什么区别?
广度优先搜索使用队列,一圈一圈均匀扩展。深度优先搜索使用栈(或递归),沿一条路径尽量深入,走不通再回退。BFS 能找到边数最少的最短路径;DFS 不能,但它很适合找环和做拓扑排序。
广度优先搜索有多快?
每个节点出队一次,每条边从两端各看一次,所以工作量随节点数加边数增长。
我的图会被发送到别处吗?
不会。图在你的浏览器中生成和搜索,上次的设置保存在此浏览器的本地存储中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器