欢迎大家订阅【蓝桥杯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（深度优先搜索）	n重循环
结构	基于递归或栈的算法，遍历图或树的节点，适合路径和连通性问题	用于多维数组、组合和暴力解法，主要处理遍历问题
回溯与非回溯	通常涉及回溯：当一条路径探索失败时返回并尝试其他路径	不涉及回溯，通常完全遍历每个组合或所有可能性
实现方式	递归/栈结构，深度优先地探索树或图的节点	嵌套循环结构，逐层遍历每种组合情况
应用场景	图/树遍历、路径查找、连通性检测、组合问题等	多维数组遍历、排列组合问题、穷举解空间等
相似性	DFS可以看作是“带回溯的循环”，递归结构类似嵌套循环	n重循环适用于处理解空间的所有可能性，也可以模拟DFS
多重DFS	在组合问题中，可能需要多个DFS组合遍历类似多重循环	多重循环用于遍历多个维度的数据或组合，适用于暴力破解

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

①DFS方法（递归）：

def dfs(node, path, all_paths):if node is None:returnpath.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 = 0def dfs(depth, n, m):# depth：第几个小朋友# n：第一种糖果剩余量# m：第二种糖果剩余量# 当分完所有小朋友后保证手上没有糖果if depth == 7:if n == 0 and m == 0:global ansans += 1return# 枚举当前小朋友的糖果可能性# 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