DFS深度优先搜索

概念引入

DFS 全称是 Depth First Search，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。
DFS 常常用来指代用递归函数实现的搜索，但实际上两者并不一样。
在 搜索算法 中，该词常常指利用递归函数方便地实现暴力枚举的算法，与图论中的 DFS 算法有一定相似之处，但并不完全相同。

在该文章中 仅讨论DFS搜索算法

DFS 搜索算法

例题p1706

1
2
3
按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

1≤n≤9

思考

循环求解

哎？拿到这道题，第一想法是不是可以循环求解？
但是怎么用循环求解呢？
循环嵌套！！

因为这不是本文所讨论的方法，在这引用洛谷的一个题解 循环求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a[10];
    for (int i = 1; i <= 9; i++)
        a[i] = i;
    int n;
    cin >> n;
    for (int i1 = 1; i1 <= n; i1++) // 把第一个数从1-n枚举
    {
        if (n == 1) // 如果n是1，即从1-1全排序
        {
            cout << "    " << i1 << "\n" // 输出全排序结果
                continue;                // 跳过后面几个数的枚举
        }
        for (int i2 = 1; i2 <= n; i2++) // 把第二个数从1-n枚举 ，后面嵌套的for循环同理，即把第3、4、5...9个数枚举
        {
            if (i2 == i1)
                continue; // 当i2和前面的数重复时，跳过后面的判断，继续循环。后面嵌套的循环同理，即当i3、i4、i5、......i9和前面数重复时，跳过后面的判断，继续循环
            if (n == 2)   // 如果n是2 ，即从1-2全排序。后面同理，即从1-3、1-4......1-9全排序
            {
                cout << "    " << i1 << "    " << i2 << "\n"; // 输出全排序结果，后面同理
                continue;                                     // 跳过后面几个数的枚举，后面同理
            }
            for (int i3 = 1; i3 <= n; i3++)
            {
                if (i3 == i2 || i3 == i1)
                    continue;
                if (n == 3)
                {
                    cout << "    " << i1 << "    " << i2 << "    " << i3 << "\n";
                    continue;
                }
                for (int i4 = 1; i4 <= n; i4++)
                {
                    if (i4 == i3 || i4 == i2 || i4 == i1)
                        continue;
                    if (n == 4)
                    {
                        cout << "    " << i1 << "    " << i2 << "    " << i3 << "    " << i4 << "\n";
                        continue;
                    }
                    for (int i5 = 1; i5 <= n; i5++)
                    {
                        if (i5 == i4 || i5 == i3 || i5 == i2 || i5 == i1)
                            continue;
                        if (n == 5)
                        {
                            cout << "    " << i1 << "    " << i2 << "    " << i3 << "    " << i4 << "    " << i5 << "\n";
                            continue;
                        }
                        for (int i6 = 1; i6 <= n; i6++)
                        {
                            if (i6 == i5 || i6 == i4 || i6 == i3 || i6 == i2 || i6 == i1)
                                continue;
                            if (n == 6)
                            {
                                cout << "    " << i1 << "    " << i2 << "    " << i3 << "    " << i4 << "    " << i5 << "    " << i6 << "\n";
                                continue;
                            }
                            for (int i7 = 1; i7 <= n; i7++)
                            {
                                if (i7 == i6 || i7 == i5 || i7 == i4 || i7 == i3 || i7 == i2 || i7 == i1)
                                    continue;
                                if (n == 7)
                                {
                                    cout << "    " << i1 << "    " << i2 << "    " << i3 << "    " << i4 << "    " << i5 << "    " << i6 << "    " << i7 << "\n";
                                    continue;
                                }
                                for (int i8 = 1; i8 <= n; i8++)
                                {
                                    if (i8 == i7 || i8 == i6 || i8 == i5 || i8 == i4 || i8 == i3 || i8 == i2 || i8 == i1)
                                        continue;
                                    if (n == 8)
                                    {
                                        cout << "    " << i1 << "    " << i2 << "    " << i3 << "    " << i4 << "    " << i5 << "    " << i6 << "    " << i7 << "    " << i8 << "\n";
                                        continue;
                                    }
                                    for (int i9 = n; i9 <= n; i9++)
                                    {
                                        if (i9 == i8 || i9 == i7 || i9 == i6 || i9 == i5 || i9 == i4 || i9 == i3 || i9 == i2 || i9 == i1)
                                            continue;
                                        cout << "    " << i1 << "    " << i2 << "    " << i3 << "    " << i4 << "    " << i5 << "    " << i6 << "    " << i7 << "    " << i8 << "    " << i9 << "\n";
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return 0;
}

可以看到，如果使用循环嵌套去解决，会非常非常麻烦（虽然这个题解还有优化的空间）。那么如果使用递归求解呢？

递归求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

int n;
int st[15];
bool num[15]; // 大小设置大一点 防止越界

void rec(int t)
{
	if (t == 0) {
		for (int i = 0; i < n; i++) 
			printf("%5d", st[i]);
			
		putchar('\n');
		return;
	}
	
	for (int i = 1; i <= n; i++)
	{
		if (num[i]) continue;
		
		num[i] = true;
		st[n-t] = i;
		rec(t-1);
		num[i] = false;
	}
}

int main()
{
	scanf("%d", &n);
	rec(n);

	return 0;
}

有没有发现，在这个递归求解的方案中，递归会一路走到头，然后再输出解。其实这就是 DFS深度优先搜索 算法的思路。

算法思路分析

DFS算法的思路就是先一条路走到黑，如果行不通，就回溯到上一个节点，走另一条路，直到所有路径都走了一遍。
引用oi-wiki

1
2
3
4
5
6
7
8
DFS(v) // v 可以是图中的一个顶点，也可以是抽象的概念，如 dp 状态等。
在 v 上打访问标记
for u in v 的相邻节点
    if u 没有打过访问标记 then
      DFS(u)
    end
  end
end

对于例题，用DFS方法求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;

const int MAX = 20;

int n;
int num[MAX];
bool vis[MAX];

void dfs(int dep)
{
    if (dep == n+1)
    {
        for (int i = 1; i <= n; i++) 
            printf("%5d", num[i]);
        putchar('\n');
        return;
    }

    for (int i = 1; i <= n; i++)
    {
        if (vis[i]) continue;

        vis[i] = true;
        num[dep] = i;

        dfs(dep+1);

        vis[i] = false;
    }
}

int main()
{
    scanf("%d", &n);
    dfs(1);
    return 0;
}

在此，使用流程图的方式展示该方法的求解过程


graph TD
    start["开始: dfs(1)"]

    %% 第一层决策
    n1["选择1: num[1]=1, vis[1]=true"]
    n2["选择2: num[1]=2, vis[2]=true"]
    n3["选择3: num[1]=3, vis[3]=true"]
    
    %% 第二层决策（从选择1出发）
    n1_2["选择2: num[2]=2, vis[2]=true"]
    n1_3["选择3: num[2]=3, vis[3]=true"]
    
    %% 第二层决策（从选择2出发）
    n2_1["选择1: num[2]=1, vis[1]=true"]
    n2_3["选择3: num[2]=3, vis[3]=true"]
    
    %% 第二层决策（从选择3出发）
    n3_1["选择1: num[2]=1, vis[1]=true"]
    n3_2["选择2: num[2]=2, vis[2]=true"]
    
    %% 第三层决策
    n1_2_3["选择3: num[3]=3, vis[3]=true"]
    n1_3_2["选择2: num[3]=2, vis[2]=true"]
    n2_1_3["选择3: num[3]=3, vis[3]=true"]
    n2_3_1["选择1: num[3]=1, vis[1]=true"]
    n3_1_2["选择2: num[3]=2, vis[2]=true"]
    n3_2_1["选择1: num[3]=1, vis[1]=true"]
    
    %% 输出结果
    out1["输出: 1 2 3"]
    out2["输出: 1 3 2"]
    out3["输出: 2 1 3"]
    out4["输出: 2 3 1"]
    out5["输出: 3 1 2"]
    out6["输出: 3 2 1"]

    %% 连接图
    start --> n1
    start --> n2
    start --> n3

    subgraph path1["路径1"]
        n1 --> n1_2
        n1 --> n1_3
        
        n1_2 --> n1_2_3
        n1_2_3 --> out1
        
        n1_3 --> n1_3_2
        n1_3_2 --> out2
    end

    subgraph path2["路径2"]
        n2 --> n2_1
        n2 --> n2_3
        
        n2_1 --> n2_1_3
        n2_1_3 --> out3
        
        n2_3 --> n2_3_1
        n2_3_1 --> out4
    end

    subgraph path3["路径3"]
        n3 --> n3_1
        n3 --> n3_2
        
        n3_1 --> n3_1_2
        n3_1_2 --> out5
        
        n3_2 --> n3_2_1
        n3_2_1 --> out6
    end

    %% 样式设置
    classDef start fill:#9cf,stroke:#333,stroke-width:2px;
    classDef node fill:#cfc,stroke:#333,stroke-width:1px;
    classDef output fill:#fcf,stroke:#333,stroke-width:1px;
    classDef back fill:#fcc,stroke:#333,stroke-width:1px;
    
    class start start;
    class n1,n2,n3,n1_2,n1_3,n2_1,n2_3,n3_1,n3_2,n1_2_3,n1_3_2,n2_1_3,n2_3_1,n3_1_2,n3_2_1 node
    class out1,out2,out3,out4,out5,out6 output
    class back1,back2,back3 back

（回溯等哪天有时间再补吧）

学习笔记
#学习笔记 #c/c++ #算法
DFS深度优先搜索
http://blog.cat-boy.cn/2025/03/18/算法-DFS深度优先搜索/
作者
HuaLiMao-AQ
发布于
2025年3月18日
许可协议