100种算法【Python版】第10篇——深度优先搜索

本文目录

• 1 深度优先搜索
• 2 示例说明：迷宫路径查找
• • 2.1 问题描述
  • 2.2 DFS解决逻辑
  • 2.3 python代码
• 3 算法应用
• • 3.1 数独问题
  • • 3.1.1 DFS求解逻辑
    • 3.1.2 python代码
  • 3.2 单词搜索
  • • 3.2.1 python代码
    • 3.2.2 代码逻辑
• 4 总结
• • 4.1 优点
  • 4.2 缺点

1 深度优先搜索

深度优先搜索（Depth-First Search, DFS）是一种用于遍历或搜索树或图的算法。通过探索尽可能深的分支，DFS 采用递归或迭代的方式实现，直到不能再继续为止，然后回溯到上一个节点继续探索其他分支。

基本原理
DFS 的核心思想是尽可能深地访问每一个节点。当到达一个节点的所有邻接节点都已经被访问过后，算法会回溯到该节点的父节点，继续遍历其他未被访问的节点。这个过程可以通过递归或使用栈来实现。

DFS 的具体步骤
(1)选择起始节点：选择一个未访问的节点作为起始点。
(2)访问节点：将该节点标记为已访问，可以进行某种处理（如打印该节点）。
(3)递归访问相邻节点：对每一个未被访问的邻接节点，递归执行 DFS。
(4)回溯：当所有邻接节点都被访问后，回到上一个节点，探索其他未访问的邻接节点。
(5)重复：直到所有节点都被访问。

实现方式
DFS 可以通过递归或栈实现。