- 当前
- 栈中
- 已完成
- 路径
深度优先搜索 (DFS)
深度优先搜索探索图的方式,就像一只手扶着墙走迷宫:沿着一条路一直走到头,只有无路可走时才退回。它靠栈来做到这一点。点击一个节点从它开始,也可以选一个终点,然后逐步查看搜索过程:栈的增长和缩短、每个节点得到的访问序号,以及构成环的边。 按“播放”观看搜索过程,或用“单步”和“后退”一步一步查看。拖动步骤滑块可跳到任意位置。点击节点可将其设为起点;把点击切换为“终点”,再点击另一个节点,即可查找到它的路径。每个节点上的数字是它被访问的顺序,图下方的一行是栈,从起点一直到栈顶的节点。“新图”会生成另一张图;可选择节点数和边数。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 跳到开头和结尾。
它是如何运作的
- 点击一个节点设为起点。要查找路径,把点击切换为“终点”,再点击另一个节点。
- 按“播放”,或用“单步”和“后退”一步一步移动。拖动步骤滑块可跳到搜索中的任意位置。
- 观察图下方的栈和每个节点上的访问序号。“新图”会生成另一张图供你尝试。
深度优先搜索的原理
把起点放入栈中。然后重复:查看栈顶节点的下一个邻居。尚未见过的邻居得到下一个访问序号,记住它是从哪个节点到达的,并放到栈顶,于是搜索从那里继续。当栈顶节点没有剩下要检查的邻居时,它就完成了,从栈中移出,搜索退回到它下面的节点。栈空时,所有能到达的节点都已访问。
栈能告诉你什么
因为搜索总是从最新的节点继续,栈始终是一条从起点到当前查看节点的路径。到达终点时,栈就是一条通向它的路径,但通常不是最短的:最短路径要靠广度优先搜索。在无向图中,指向仍在栈中的节点(刚来的那个除外)的边会构成一个环。记住的这些节点组成一棵树,即深度优先树,而节点完成的顺序是拓扑排序的关键。
常见问题
什么是深度优先搜索?
一种从起点探索图的方法:沿着一条路尽可能深入,只有无路可走时才退回去尝试另一个分支。它用栈或递归来记住回去的路。
深度优先搜索能找到最短路径吗?
不能。如果存在通向终点的路径,它能找到一条,但这条路径可能比需要的长得多,因为 DFS 会一直沿着它尝试的第一个分支走下去。要找边数最少的路径,请用广度优先搜索;边有长度时,请用 Dijkstra 算法。
DFS 和 BFS 有什么区别?
深度优先搜索使用栈,先沿一条路走深,再退回。广度优先搜索使用队列,一圈一圈均匀地向外扩展。两者访问所有可到达节点的时间都随节点数加边数增长;BFS 能找到最短路径,而 DFS 是处理环、迷宫和拓扑排序的自然选择。
DFS 如何找到环?
在无向图中,如果搜索遇到一条指向仍在栈中的节点的边,而那个节点不是刚来的节点,这条边就构成了一个环。在本应用中,出现这种情况时状态栏会提示。
我的图会被发送到别处吗?
不会。图在你的浏览器中生成和搜索,上次的设置保存在此浏览器的本地存储中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器