深度优先搜索dfs(附带例题)

先给大家说一下dfs和bfs大概的区别：

• dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。
• bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。

以上述卡哥图片来简单解析一下深度优先搜索：

从1开始出发，有三条路径可以选，随机选择一条一直走，直到遇到目的地或者是访问过的位置，这样才会进行回溯(这就找到了终止条件)。假设从1走到5，再由5走到6，到达目的地，开始去搜索其他方向，撤销离结束最近的一条路径，也就是从5到6的这条路径。撤销之后起步位置又到了5，5这里只有两条路径可走，所以由5到4，再由4到6，到达目的地，又开始回溯。撤销4到6的路径，4到3，3到6，回溯到3，再由3到2，2到4或到1都是访问过的点，所以2回溯到3，由3再到目的地。之后再回溯…………

但关键就两点：

• 搜索方向，是认准一个方向搜，直到碰壁之后再换方向
• 换方向是撤销原路径，改为节点链接的下一个路径，回溯的过程

因为递归也有回溯过程，所以深搜可以类比递归。

深搜三部曲：

1.确认递归函数，参数

void dfs(参数)

深搜需要二维数组保存符合条件的所有路径，需要一维数组保存单一路径，这种保存结果的数组，可以用全局变量来定义，避免函数参数过多。

2.确认终止条件

if (终止条件) {
存放结果;
return;
}

3.处理目前搜索节点出发的路径

for (选择：本节点所连接的其他节点) {
处理节点;
dfs(图，选择的节点); // 递归
回溯，撤销处理结果
}

用一个for循环遍历目前搜索节点所能到的所有节点。

void dfs(参数) {
if (终止条件) {
存放结果;
return;
}

for (选择：本节点所连接的其他节点) {
处理节点;
dfs(图，选择的节点); // 递归
回溯，撤销处理结果
}
}

1.深搜例题——可达路径

题目描述

给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个函数，找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。

输入描述

第一行包含两个整数 N，M，表示图中拥有 N 个节点，M 条边

后续 M 行，每行包含两个整数 s 和 t，表示图中的 s 节点与 t 节点中有一条路径

输入示例

5 5
1 3
3 5
1 2
2 4
4 5

输出示例

1 3 5
1 2 4 5

提示信息

用例解释：

有五个节点，其中的从 1 到达 5 的路径有两个，分别是 1 -> 3 -> 5 和 1 -> 2 -> 4 -> 5。

因为拥有多条路径，所以输出结果为：

1 3 5 1 2 4 5

或

1 2 4 5 1 3 5 都算正确。

数据范围：

• 图中不存在自环
• 图中不存在平行边
• 1 <= N <= 100
• 1 <= M <= 500

#include <stdio.h>
#include <stdlib.h>

int** result; // 收集符合条件的路径
int* result_sizes; // 每条路径的长度
int result_size = 0; // 结果路径数量

int* path; // 1节点到终点的路径
int path_size = 0; // 当前路径长度

int max_paths = 1000; // 最大路径数估计值（根据题目范围设置）

void dfs(int** graph, int x, int n) {
// 当前遍历的节点x 到达节点n
if (x == n) { // 找到符合条件的一条路径
// 分配内存存储当前路径
result[result_size] = malloc(path_size * sizeof(int));
for (int i = 0; i < path_size; i++) {
result[result_size][i] = path[i];
}
result_sizes[result_size] = path_size;
result_size++;
return;
}

for (int i = 1; i <= n; i++) { // 遍历节点x链接的所有节点
if (graph[x][i] == 1) { // 找到 x链接的节点
path[path_size++] = i; // 遍历到的节点加入到路径中来
dfs(graph, i, n); // 进入下一层递归
path_size–; // 回溯，撤销本节点
}
}
}

int main() {
int n, m, s, t;
scanf("%d %d", &n, &m);

// 1. 分配邻接矩阵内存，节点编号从1到n，所以申请 n+1 这么大的数组
int** graph = (int**)malloc((n + 1) * sizeof(int*));
for (int i = 0; i <= n; i++) {
graph[i] = (int*)calloc((n + 1), sizeof(int)); // 初始化为0
}

// 2. 分配结果数组内存（估计一个最大路径数）
result = (int**)malloc(max_paths * sizeof(int*));
result_sizes = (int*)malloc(max_paths * sizeof(int));

// 3. 分配路径数组内存（最大长度不超过n）
path = (int*)malloc((n + 1) * sizeof(int));

// 读取边信息
while (m–) {
scanf("%d %d", &s, &t);
// 使用邻接矩阵表示无向图，1 表示 s 与 t 是相连的
graph[s][t] = 1;
}

// 无论什么路径已经是从1节点出发
path[0] = 1;
path_size = 1;

dfs(graph, 1, n); // 开始遍历

// 输出结果
if (result_size == 0) {
printf("-1\\n");
} else {
for (int i = 0; i < result_size; i++) {
for (int j = 0; j < result_sizes[i] – 1; j++) {
printf("%d ", result[i][j]);
}
printf("%d\\n", result[i][result_sizes[i] – 1]);//保证最后一个节点后面没有空格
}
}

// 释放内存
for (int i = 0; i < result_size; i++) {
free(result[i]);
}
free(result);
free(result_sizes);

for (int i = 0; i <= n; i++) {
free(graph[i]);
}
free(graph);

free(path);

return 0;
}

图的存储

有两种存储方式：邻接表和邻接矩阵

上述代码用的是邻接矩阵。

邻接矩阵使用二维数组来表示图结构。邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。

本题有n个节点，但节点标号是从1开始的，为了节点标号和下标对齐，所以申请（n+1）*（n+1）这么大的二维数组。

while (m–) {
scanf("%d %d", &s, &t);
// 使用邻接矩阵表示无向图，1 表示 s 与 t 是相连的，同时表示节点s指向节点t
graph[s][t] = 1;
}

深搜三部曲：

1.确认递归函数，参数

dfs函数参数肯定要存一个图的，用来遍历的；需要存目前我们遍历的节点，定义为x；还要存一个n，表示终点；我们在遍历的时候，用于判断当x==n时，说明找到了终点。

2.确认终止条件

当目前遍历的节点为最后一个节点n的时候，就找到了一条从出发点到终止点的路径。

// 当前遍历的节点x 到达节点n
if (x == n) { // 找到符合条件的一条路径
add_to_result(path, path_size);
return;
}

3.处理目前搜索节点出发的路径

接下来是走当前遍历节点的下一个节点。首先要找到x节点指向了哪些节点，这样才能把下一个节点放到路径中，然后再将下一个节点作为递归的起点进行递归过程…………

回溯过程是怎么执行的？递归过程很重要

remove_from_path(); // 回溯，撤销本节点。

    1    / \\   2   3    \\ /     4

以上述为例解析一下，

从节点1开始探索邻居2：

// 在dfs(graph, 1, 4)中
for (i = 1; i <= 4; i++) {
if (graph[1][2] == 1) { // 找到邻居2
add_to_path(2); // path = [1, 2]
dfs(graph, 2, 4); // 递归调用 ← 进入新的函数调用
// ↓↓↓ 注意：这里还没执行到remove_from_path()
}
}

进入dfs(graph,2,4):

// 这是一个新的函数调用栈
void dfs(graph, 2, 4) {
if (2 == 4) … // false，不执行

for (i = 1; i <= 4; i++) {
if (graph[2][4] == 1) { // 遍历找到邻居4
add_to_path(4); // path = [1, 2, 4]
dfs(graph, 4, 4); // 递归调用
// ↓↓↓ 注意：这里还没执行到remove_from_path()
}
}
// 当for循环结束时，dfs(graph, 2, 4)函数执行完毕
// 函数返回，控制权交还给上一层调用
}

进入dfs(graph, 4, 4)：

void dfs(graph, 4, 4) {
if (4 == 4) { // true，到达目的地
add_to_result(path, path_size); // 保存路径[1, 2, 4]
return; // 立即返回，不执行后面的for循环
}
// … 这里不会执行
}
// dfs(graph, 4, 4)执行完毕，返回到dfs(graph, 2, 4)

回到dfs(graph, 2, 4)：

// 现在回到dfs(graph, 2, 4)中add_to_path(4)的后面：
add_to_path(4); // path = [1, 2, 4]
dfs(graph, 4, 4); // 已返回 ↑
remove_from_path(); // ← 现在执行回溯！path = [1, 2] (移除4)

// 继续for循环，检查节点2的其他邻居
// 假设graph[2][1]==0, graph[2][3]==0…
// for循环结束
}
// dfs(graph, 2, 4)函数执行完毕，返回

回到dfs(graph, 1, 4)：

// 现在回到dfs(graph, 1, 4)中add_to_path(2)的后面：
add_to_path(2); // path = [1, 2]
dfs(graph, 2, 4); // 已返回 ↑
remove_from_path(); // ← 现在执行回溯！path = [1] (移除2)

// 继续for循环，探索节点1的下一个邻居3…

"递归完成返回"和"回溯"是先后关系：

正式开始解析上述代码：

1.分析上述代码全局变量的作用和意义

int** result;存储所有从起点到终点的路径。符合上述深搜三部曲中，深搜需要二维数组保存符合条件的所有路径。

• result 是一个指针数组（二级指针）

• result[i] 是第i条路径（一个一维数组）

• result[i][j] 是第i条路径上的第j个节点

根据上述分析可以得知int** result;可以转换成int result[][];但是由于上述代码用的是邻接矩阵，提前不能得知数组的大小，所以只能利用二级指针。

如果找到两条路径 [1,2,4] 和 [1,3,4]
result[0] → [1, 2, 4] // 第一条路径
result[1] → [1, 3, 4] // 第二条路径

根据上述result[0][],result[1][]说明，需要一个变量来记录已经找到了多少条路经，而这个变量用result_size来表示，result_size是result数组的第一个[]。根据上述result[0] → [1, 2, 4],说明还需要一个变量来表示1，2，4这些可以到达目的地的节点,即可以到达目的地的节点数目，通过for循环将节点都存储到这条路径中来，所以result第二个[]用i来表示，但范围是节点数目，用变量path_size来表示。但将节点存储起来给result数组的是用另一个数组path[]，用变量int* path;来表示。

为什么用一个一维数组指针来表示而不用整数型变量来表示呢？肯定是因为我们一开始不知道哪些节点会到达目的地，所以要把所有的节点以数组的形式存储起来，而path数组就是存储节点的，根据条件来找到可以到达目的地的节点。

上述基本上已经解释清楚为什么需要这些变量了，还有就是，已经招到可以到达目的地的路径了，现在要输出，result_size=0表示第一条路经，作为外层循环；那什么作为内层循环输出符合题意的这几个节点呢？回想一下，我们之前将符合题意的节点放到result数组中时，用的是i，同时path_size作为范围变量。但现在是所有正确路径都找到之后再进行输出操作，所以不能和上面一样找到一条路径就输出。所以我们要定义另一个数组进行输出操作。这里用的是result_sizes数组，和result数组用同一个表示路径条数的变量result_size表示数组下标，然后将path_size范围变量作为值。

回溯的时候，就是要将最近的这条路径撤销，也就是正确路径的最后一个到达目的地的路径被撤销。根据上述表示节点数目的是path_size，所以回溯就是path_size–;

注意在主函数中一开始初始化path[0]=1；

int* result_sizes;记录每条路径包含多少个节点。

• result_sizes[i] 表示第i条路径的长度（节点数）

路径1: [1,2,4] → 长度3 → result_sizes[0] = 3
路径2: [1,3,4] → 长度3 → result_sizes[1] = 3

int result_size = 0;记录已经找到了多少条路径

初始化为0，如果找到了路径，可以作为第一条路经。

int* path;存储当前正在探索的节点1到目标节点n的路径；整型指针，指向动态分配的数组。

内存分配：path = (int*)malloc((n + 1) * sizeof(int)）注意分配n+1个整数空间

路径 [1, 2, 4, 5] 在内存中：
path[0] = 1
path[1] = 2
path[2] = 4
path[3] = 5

特点：

动态分配，大小根据输入的n确定。但注意使用后需要手动释放：free(path).

int path_size = 0; 记录path数组当前有多少个有效节点。初始是空路径，所以初始化为0.

// 添加节点到路径
path[path_size++] = i; // path_size增加1

// 从路径移除节点（回溯）
path_size–; // path_size减少1
示例流程：
初始：path_size = 0
添加节点1：path[0]=1, path_size=1
添加节点2：path[1]=2, path_size=2
添加节点4：path[2]=4, path_size=3
回溯：path_size=2（虽然path[2]的值还在，但被视为无效）

path_size是数组的逻辑长度，不是物理长度。有效节点是从path[0]到path[path_size-1]。

int max_paths = 1000;预分配结果数组时使用的最大路径数估计

2.为什么需要这个预分配？

需要预分配result数组来存储找到的所有路径；不知道实际会有多少条路径；必须要估计一个足够大的值来避免数组越界。

result = (int**)malloc(max_paths * sizeof(int*));
result_sizes = (int*)malloc(max_paths * sizeof(int));

3.解析一下动态内存分配数组:

因为我们将下标对应节点，所以分配n+1行和列。

int** graph = (int**)malloc((n + 1) * sizeof(int*));     for (int i = 0; i <= n; i++) {         graph[i] = (int*)calloc((n + 1), sizeof(int)); // 初始化为0     }

    // 2. 分配结果数组内存（估计一个最大路径数）     result = (int**)malloc(max_paths * sizeof(int*));     result_sizes = (int*)malloc(max_paths * sizeof(int));          // 3. 分配路径数组内存（最大长度不超过n）     path = (int*)malloc((n + 1) * sizeof(int));

1.int** graph = (int**)malloc((n + 1) * sizeof(int*));

作用：分配一个指针数组，用于存储n+1个行指针

因为是二维数组，所以指针指向的还是指针，现在只是分配了5个指针的内存空间

分配了 (n + 1) 个 int* 类型的空间
例如 n=4 → 分配 5 个指针的空间

内存布局：
graph → [指针0, 指针1, 指针2, 指针3, 指针4]
↓ ↓ ↓ ↓ ↓
[?] [?] [?] [?] [?] ← 每个指针还未指向具体内存
内层循环分配每行：
for (int i = 0; i <= n; i++) {
graph[i] = (int*)calloc((n + 1), sizeof(int));
}

作用：为每一行分配n+1个整数，并初始化为0.

calloc 函数与 malloc 有一个重要区别：

// malloc: 分配内存，不初始化
int* arr1 = (int*)malloc(5 * sizeof(int));
// arr1内容：随机值/未定义

// calloc: 分配内存，并初始化为0
int* arr2 = (int*)calloc(5, sizeof(int));
// arr2内容：[0, 0, 0, 0, 0]

所以 graph[i] = (int*)calloc((n + 1), sizeof(int)); 这一行：

• 分配了 (n + 1) × sizeof(int) 字节的内存

• 自动将所有字节初始化为0

那为什么邻接矩阵需要初始化所有元素为0呢？

因为我们后面用graph[i][j] = 1来表示i和j相连，所以一开始都初始化为0.

第0次循环 (i=0):
graph[0] = calloc(5, sizeof(int))
→ 分配 5×4 = 20字节，全部初始化为0
→ graph[0] 指向这个内存块

最终结果：
graph[0] → [0, 0, 0, 0, 0] ← 第0行（实际不使用）
graph[1] → [0, 0, 0, 0, 0] ← 第1行（节点1的连接情况）
graph[2] → [0, 0, 0, 0, 0] ← 第2行（节点2的连接情况）
…
graph[4] → [0, 0, 0, 0, 0] ← 第4行（节点4的连接情况）

2.result = (int**)malloc(max_paths * sizeof(int*));

作用：用于存储每条通往目的地的路径。因为一开始不确定有多少条路径可以满足题意，所以定义max_paths较大的值，分配足够多的空间存储符合题意路径。

max_paths = 1000（假设值）
分配 1000 个 int* 类型的空间

内存布局：
result → [指针0, 指针1, …, 指针999]

result_sizes = (int*)malloc(max_paths * sizeof(int));

作用：存储每条路径长度

分配 1000 个 int 类型的空间

内存布局：
result_sizes → [?, ?, ?, …, ?] ← 1000个未初始化整数
0 1 2 999

3.path = (int*)malloc((n + 1) * sizeof(int));

作用：用于存储当前路径

分配 (n + 1) 个 int 类型的空间
例如 n=4 → 分配 5 个整数的空间

内存布局：
path → [?][?][?][?][?] ← 5个未初始化整数

最长路径可能包含所有节点，所以需要 n 个位置，再加1是为了安全。

这些内存在dfs中的变化：

初始状态：
path: [?, ?, ?, ?, ?] ← 未初始化
设置后：path[0]=1，path_size=1

result: [NULL, NULL, …, NULL] ← 1000个NULL
result_sizes: [?, ?, …, ?] ← 未初始化

因为一开始不知道有多少条符合题意的路径，所以在找到一条路径后，就要再重新进行内存分配

找到第一条路径后：
// 假设找到路径 [1, 2, 4]，path_size=3
result[0] = malloc(3 * sizeof(int)); // 分配新内存
// 复制数据到 result[0] = [1, 2, 4]
result_sizes[0] = 3;
内存变化：
result[0] → 新分配的内存块 [1, 2, 4]
result_sizes[0] = 3
result_size = 1
找到第二条路径后：
// 假设找到路径 [1, 3, 4]，path_size=3
result[1] = malloc(3 * sizeof(int)); // 再分配新内存
// 复制数据到 result[1] = [1, 3, 4]
result_sizes[1] = 3;
内存变化：
result[0] → [1, 2, 4]
result[1] → [1, 3, 4] ← 新分配的
result_sizes[0] = 3
result_sizes[1] = 3
result_size = 2

4.内存释放

程序结束前必须要释放所有分配的内存：

释放内存的顺序应该与分配顺序相反（从内到外）主要取决于依赖关系：

分配顺序：

释放顺序：

按照依赖关系释放：

1.先释放被依赖的数据（内层数据）：

for (i < result_size) free(result[i]); // 路径数据被result指针引用
for (i <= n) free(graph[i]); // 行数据被graph指针引用

2.再释放指针数组（外层指针）：

free(result); // 现在可以安全释放指针数组
free(graph); // 现在可以安全释放指针数组

3.最后释放独立数组：

free(result_sizes); // 独立，不引用其他内存
free(path); // 独立，不引用其他内存

独立数组可以在任意位置释放，但通常在相关系统释放后释放。