深度优先搜索 (DFS)
走进迷宫,一直走到死胡同,然后退回最近的岔路口,试下一条路。深度优先搜索就是这样探索图的。它是最简单的图算法之一,而它维护的栈能告诉你的东西比你想象的更多。
基本思路
图是由边连接起来的一组节点:房间和门、网页和链接、任务和它们所依赖的任务。深度优先搜索会访问从起点能到达的每个节点,但按特定的顺序:它总是从最近到达的节点继续。它维护一个栈,存放它所在的那些节点。新节点放到栈顶,只有当一个节点周围的一切都探索完,它才会被移出。
分步说明
把起点放入栈中,给它访问序号 1。查看栈顶节点的下一个邻居。如果它没见过,就给它下一个访问序号,记住它是从哪个节点到达的,并把它放到栈顶。如果见过,就跳过。当栈顶节点没有剩下要检查的邻居时,它就完成了:把它移出,继续处理下面的节点。栈空或到达终点时停止。
示例
取一张有边 A–B、A–C、B–D、C–D、C–E 和 D–F 的图,从 A 开始,按字母顺序检查邻居。搜索从 A 到 B,从 B 到 D,从 D 到 C,再从 C 到 E,所以栈是 A, B, D, C, E。途中,C 看到仍在栈中的 A:边 C–A 构成了环 A, B, D, C。E 没有新的邻居,所以它完成了,接着 C 也完成,搜索退回到 D,D 还有 F。访问顺序是 A, B, D, C, E, F。如果以 E 为终点,DFS 会停在路径 A → B → D → C → E 上,共四条边,而 A → C → E 只需两条。
用途
栈始终是一条从起点到当前节点的路径,这使 DFS 天然适合迷宫和谜题:这正是回溯的思想。在无向图中,指向仍在栈中的节点的边会构成环。在有向图中,按节点完成顺序的逆序列出节点,就得到拓扑序,使每个任务都排在它所依赖的任务之后。深度优先搜索还能找出连通分量、桥和割点,它的随机版本是生成迷宫的经典方法。
历史
19 世纪,法国数学家 Charles Pierre Trémaux 描述了一种通过标记通道走出任何迷宫的方法,这就是用粉笔完成的深度优先搜索。1972 年和 1973 年,Robert Tarjan 和 John Hopcroft 证明,DFS 能在线性时间内解决许多图问题,从强连通分量到判断一张图能否画成没有交叉的样子。他们获得 1986 年图灵奖,部分正是因为这项工作。
动手试试
打开应用,按“单步”。正在检查邻居的节点会高亮显示,栈中的节点为蓝色,已完成的节点为绿色,每个节点都标有访问序号。栈显示在图的下方,从起点到栈顶的节点。留意状态栏中构成环的边,并选择一个终点,看看与广度优先搜索相比,找到的路径可能长多少。
常见问题
DFS 的时间复杂度是多少?
O(V + E),其中 V 是节点(顶点)数,E 是边数:每个节点进栈、出栈各一次,每条边从两端各检查一次。它还需要 O(V) 的额外内存来存放栈和标记。
DFS 为什么使用栈?
因为后进先出让搜索从最新的节点继续,并退回到它之前的节点。递归借助程序的调用栈做的是同一件事。如果改用队列,搜索就会一圈一圈向外扩展:那就是广度优先搜索。
递归 DFS 对大图有问题吗?
可能有:路径长就意味着递归深,而许多语言会限制调用的深度。在循环中使用显式的栈可以避开这个限制,同时按相同的顺序访问节点。
DFS 用在哪里?
用回溯法解迷宫和谜题、查找环、按依赖关系给任务排序(拓扑排序)、找出连通分量和强连通分量、生成迷宫,以及在遍历依赖图的编译器和构建工具中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
试试深度优先搜索