Depth-First Search

释义 Definition

深度优先搜索（DFS）：一种遍历/搜索图或树的算法策略，优先沿着一条路径尽可能深入，直到无法继续再回溯（常用递归或栈实现）。常用于路径探索、连通性判断、拓扑排序等。（也有其他相关含义与变体，如迭代加深等。）

发音 Pronunciation (IPA)

/depθ fst st/（BrE）, /dpθ fst st/（AmE）

例句 Examples

Depth-first search visits nodes by going as deep as possible first.
深度优先搜索会先尽可能向更深的节点访问。

In this maze solver, depth-first search explores one corridor to the end before backtracking, which can be faster but may miss the shortest route.
在这个迷宫求解器中，深度优先搜索会先把一条通道走到底再回溯，这可能更快，但未必能找到最短路径。

词源 Etymology

该术语由 depth（深度）+ first（优先）+ search（搜索） 组成，字面意思是“先追求深度的搜索”。在计算机科学中用来描述一种系统的探索顺序，常与 breadth-first search（广度优先搜索） 形成对比：DFS偏“深入再回退”，BFS偏“分层扩展”。

相关词 Related Words

• Backtracking
• Breadth-First Search
• Graph
• Tree
• Recursion
• Stack
• Traversal
• Topological Sort

文献与作品 Literary Works

• Introduction to Algorithms（CLRS）在图算法章节中系统讲解DFS及其应用（如拓扑排序、强连通分量等）。
• Artificial Intelligence: A Modern Approach（Russell & Norvig）在搜索与状态空间探索中提及DFS及相关策略。
• Algorithms（Sedgewick & Wayne）以实现与可视化方式介绍DFS在图/树遍历中的用法。
• The Art of Computer Programming, Volume 1（Knuth）在基础算法与数据结构讨论中涉及与DFS相关的遍历思想与实现工具（如栈/递归）。