深度优先搜索与剪枝策略

# 一、深度优先搜索（DFS）简介

深度优先搜索（Depth First Search，DFS）是一种用于遍历或搜索树或图的算法。在DFS算法中，从起始顶点开始，沿着一条路径尽可能深的搜索，直到到达最远的顶点，然后回溯，继续搜索其他路径。DFS通常利用递归或栈来实现。

## 1.1 什么是深度优先搜索？

深度优先搜索是一种重要的图搜索算法，它适用于目标多样且解题路径不唯一的问题。DFS通过不断地向纵向或深度方向前进，直到不能前进为止，然后返回，开始探索下一个分支。在搜索过程中，它能记录访问过的节点以及从根节点到当前节点的路径。

## 1.2 深度优先搜索的基本原理

DFS的基本原理是深入探索图中的每一个分支，对于每一个节点，都尽可能深的搜索，直到到达叶子节点为止。在搜索过程中需要标记已访问的节点，以避免重复访问。

## 1.3 深度优先搜索的应用场景

深度优先搜索广泛应用于解决图论中的路径查找问题，如迷宫求解、拓扑排序、有向图中的环检测等。此外，在人工智能的状态空间搜索、模式匹配和博弈树的构建中，DFS也有着重要的应用。

以上是深度优先搜索的简介，接下来我们将重点讨论深度优先搜索的算法实现。
### 二、 深度优先搜索的算法实现

在本章中，我们将详细介绍深度优先搜索算法的实现方式，包括递归实现和栈实现。深度优先搜索是一种用于遍历或搜索树或图的算法，通过优先访问子节点而继续搜索，直到达到最深的节点，然后再回溯到前面的节点进行其他路径的搜索。

#### 2.1 递归实现深度优先搜索

递归实现是深度优先搜索算法最直接的实现方式之一。通过递归调用自身来实现对每个节点的访问，直到达到终止条件。下面以二叉树为例，演示递归实现深度优先搜索的代码：

# Python 递归实现深度优先搜索
class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.val = value
        self.left = left
        self.right = right

def dfs_recursive(node):
    if node is None:
        return
    print(node.val)  # 访问节点的操作
    dfs_recursive(node.left)
    dfs_recursive(node.right)

# 创建二叉树
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
dfs_recursive(root)

上述代码定义了一个简单的二叉树结构，并使用递归方式实现了深度优先搜索，当运行该代码时，输出结果为：1, 2, 4, 5, 3，即按照深度优先的顺序访问了二叉树的所有节点。

#### 2.2 栈实现深度优先搜索

除了递归实现外，使用栈（Stack）也是一种常见的深度优先搜索的实现方式。通过栈来模拟递归过程，实现对每个节点的访问。

下面是使用栈实现深度优先搜索的代码示例：

# Python 栈实现深度优先搜索
def dfs_stack(root):
    if root is None:
        return
    stack