练14：DFS基础

欢迎大家订阅【蓝桥杯Python每日一练】 专栏，开启你的 Python数据结构与算法 学习之旅！

1 DFS基础

①定义
深度优先搜索（DFS，Depth First Search）是一种用于遍历或搜索树或图的算法。

它从根节点开始，尽可能深入每个分支的节点，直到到达叶节点或没有可遍历的节点为止。如果当前节点没有未被访问的邻接节点，DFS会回溯到最近的一个节点，继续遍历未访问的邻接节点。

②基本思想

• 从起始节点出发，沿着一条路径尽可能深入。
• 如果到达了一个节点，该节点没有未访问的邻接节点（即所有的路径都已遍历完），那么回溯到上一个节点，继续查找其他未访问的邻接节点。
• 重复这一过程，直到遍历完所有节点。

③应用

• 图遍历：DFS用于图的遍历，尤其适合用来发现图的连接性，查找某一节点，检查是否存在路径等。
• 树的遍历：DFS可以用来进行树的遍历，包括前序遍历、中序遍历、后序遍历。
• 拓扑排序：在有向无环图（DAG）中，DFS可以用于生成拓扑排序。
• 路径搜索：用于在图中寻找从一个节点到另一个节点的路径。
• 图的连通性：用于检查一个图是否是连通的。

④实现

DFS可以通过递归或者栈来实现。

a. 递归实现

递归是DFS最自然的实现方式。每次递归调用代表从一个节点开始深度遍历。

def dfs_recursive(graph, node, visited):
    # 访问当前节点
    visited.add(node)
    print(node, end=" ")

    # 遍历所有邻居节点
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

说明：

• graph是图的邻接表表示，node是当前访问的节点，visited是一个集合，用于记录已访问的节点。
• 递归地访问每个邻接节点，直到没有未访问的邻接节点为止。

b. 栈实现

如果使用栈来模拟递归，可以避免递归的深度限制，同时保持DFS的深度优先特性。

def dfs_stack(graph, start):
    visited = set()  # 用于记录已访问的节点
    stack = [start]  # 用栈来模拟递归

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node, end=" ")
            visited.add(node)
            # 将所有未访问的邻接节点加入栈中
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

说明：

• 使用栈（stack）来模拟递归的函数调用栈，确保深度优先的遍历。
• 每次从栈中弹出一个节点并访问，然后将它的未访问邻接节点推入栈中。

⑤图的表示方式

DFS常见的图的表示方式是邻接表，也可以用邻接矩阵来表示。

a. 邻接表表示法

graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [1],
    4: [1],
    5: [2]
}

在邻接表中，graph[node]表示与节点node相邻的所有节点。

b. 邻接矩阵表示法

邻接矩阵是一个二维数组，matrix[i][j] = 1表示节点i和节点j之间有边，matrix[i][j] = 0表示没有边。

# 假设有6个节点，编号为0-5
matrix = [
    [0, 1, 1, 0, 0, 0],
    [1, 0, 0, 1, 1, 0],
    [1, 0, 0, 0, 0, 1],
    [0, 1, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0]
]

⑥时间复杂度和空间复杂度

a. 时间复杂度

对于一个有V个节点和E条边的图，DFS的时间复杂度是O(V + E)。

• 每个节点最多访问一次。
• 每条边最多访问一次（在无向图中，边会被两次访问）。

b. 空间复杂度

空间复杂度主要由两个因素决定：

1. 栈空间：递归时系统调用栈的深度或手动维护的栈的最大深度。最坏情况下是图的节点数V。
2. 已访问节点的存储空间：通常用一个集合或布尔数组来标记已访问节点，占用O(V)空间。

所以，DFS的空间复杂度为O(V)。

⑦特点

• 深度优先：DFS优先深入到图的某一分支，直到无法继续才回溯到上一个节点。
• 适合路径问题：DFS可以用来寻找从源节点到目标节点的路径（例如，在迷宫中寻找路径）。
• 可能产生较长的递归链：对于深度较大的图，递归调用栈可能会非常深（可能导致栈溢出）。
• 不一定找到最短路径：DFS不保证找到从源节点到目标节点的最短路径。对比广度优先搜索（BFS），BFS能够保证找到最短路径。

【示例——DFS遍历图】

假设我们有以下图的邻接表：

graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [1],
    4: [1],
    5: [2]
}

我们从节点0开始进行DFS遍历，递归实现：

visited = set()
dfs_recursive(graph, 0, visited)

输出结果：

0 1 3 4 2 5

从节点0出发，首先访问节点1，然后深入访问节点3，回溯到1，接着访问节点4，然后返回到0，访问节点2，最后访问节点5。

2 n重循环（嵌套循环）

①定义
n重循环是指使用多层嵌套的循环结构，常用于需要处理多维数组、多个条件组合或多变量问题的场景。每个循环都是上一层循环的子集，依次遍历。

②核心特点

• 嵌套：n重循环通常是多层循环结构，每一层循环的次数取决于上一层的循环状态。
• 复杂度：n重循环的时间复杂度通常是O(n^k)（其中k是循环的层数），适用于解决高维度的遍历问题。

【示例】

假设我们有一个二维数组，需要遍历所有的元素，可以使用双重循环：

# 二维数组的遍历
for i in range(m):  # 第一层循环
    for j in range(n):  # 第二层循环
        print(matrix[i][j])  # 访问二维数组的元素

对于更高维度的数组，我们就可以使用三重循环、四重循环等：

# 三维数组的遍历
for i in range(m):  # 第一层循环
    for j in range(n):  # 第二层循环
        for k in range(p):  # 第三层循环
            print(matrix[i][j][k])  # 访问三维数组的元素

③应用场景

• 多维数组/矩阵遍历：在处理多维数组、矩阵等数据结构时，需要使用嵌套循环。
• 全排列/组合问题：例如，求解n个元素的所有排列或组合时，可以使用嵌套循环遍历每一种情况。
• 暴力破解：当问题的解空间非常大，需要穷举所有可能的解时，常使用多重循环。

3 DFS与n重循环的区别与联系

【示例对比】
假设我们需要寻找一个树中的所有路径：

①DFS方法（递归）：

def dfs(node, path, all_paths):
    if node is None:
        return
    path.append(node.value)
    if not node.left and not node.right:  # 叶子节点
        all_paths.append(path.copy())
    else:
        dfs(node.left, path, all_paths)
        dfs(node.right, path, all_paths)
    path.pop()  # 回溯

# 假设tree是二叉树
all_paths = []
dfs(tree.root, [], all_paths)
print(all_paths)

②n重循环方法（在解空间已知的情况下，可以模拟组合）：

假设我们知道每一层的选择（如每一层有若干选择），可以用多重循环来遍历每一种可能的路径。

for i in range(m):  # 第一层
    for j in range(n):  # 第二层
        for k in range(p):  # 第三层
            # 访问某个路径
            print(i, j, k)

4 例题分析

题目地址：https://www.lanqiao.cn/problems/4124/learning/

【示例代码】

# ans表示方案数
ans = 0

def dfs(depth, n, m):
    # depth：第几个小朋友
    # n：第一种糖果剩余量
    # m：第二种糖果剩余量
    
    # 当分完所有小朋友后保证手上没有糖果
    if depth == 7:
        if n == 0 and m == 0:
            global ans
            ans += 1
        return

    # 枚举当前小朋友的糖果可能性
    # i 表示当前小朋友得到的第一种糖果的数量（0-5）
    for i in range(0, 6):
        # j 表示当前小朋友得到的第二种糖果的数量（0-5）
        for j in range(0, 6):
            if 2 <= i+j <=5 and i <= n and j <= m:
                # 调用dfs函数，进入下一层，处理下一个小朋友
                # 剩余的糖果数量不能为负
                dfs(depth + 1, n - i, m - j)

# 初始化递归，depth从0开始（即从第一个小朋友开始分配）
dfs(0,9,16)
print(ans)

【执行流程】
本题使用 DFS（深度优先搜索） 来逐层递归地探索所有可能的糖果分配情况，并且通过 回溯 来保证每一种分配方案的合法性。

①函数调用栈的初始化
首先，调用 dfs(0, 9, 16)，表示从第一个小朋友开始分配糖果，剩余的第一种糖果有 9 个，第二种糖果有 16 个。

②进入递归函数 dfs(depth, n, m)

第一个小朋友（depth = 0）：

• n = 9（第一种糖果剩余 9 个）
• m = 16（第二种糖果剩余 16 个）

在 depth = 0 时，程序会进入 for i in range(0, 6) 和 for j in range(0, 6) 两个嵌套循环，分别枚举每个小朋友可以收到的糖果数量 i（第一种糖果数量）和 j（第二种糖果数量）。满足条件 2 <= i + j <= 5 且 i <= n 和 j <= m，程序继续递归。

该循环会探索每种可能的糖果分配方案，并递归到下一个小朋友。

递归到下一个小朋友（depth = 1）：
递归进入下一个小朋友的分配，并且更新剩余糖果数量 n - i 和 m - j。例如，如果当前小朋友分配了 2 个糖果（1 个第一种和 1 个第二种糖果），则递归调用 dfs(1, 9 - 1, 16 - 1)，即剩余糖果为 n = 8 和 m = 15。

该过程会继续递归，直到 depth == 7。

③回溯的核心
递归调用 dfs(depth + 1, n - i, m - j) 时，n - i 和 m - j 表示剩余的糖果数量。递归过程中会试探不同的糖果分配方案，并在每个层级上回溯。

④终止条件
当递归的 depth == 7 时，说明已经分配了所有 7 个小朋友的糖果。此时，程序会检查是否所有的糖果都已经分配完：if n == 0 and m == 0。如果是，说明这是一个合法的糖果分配方案，因此 ans += 1。

⑤返回结果
当所有递归结束后，程序会输出 ans，即所有合法糖果分配方案的数量。

5067671