深度优先搜索-DFS

本文最后更新于 2024年9月18日 凌晨

栈

特点

栈是后进先出（Last In First Out）的线性表，简称LIFO表

例子

迷宫最短路问题

这个问题实际上使用DFS和BFS都可以实现,而且就找最短路来说，队列的时间复杂度更小，但是为了符合回溯这个主题，我们尝试使用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
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<stdio.h>
#include<windows.h>
char ch[10][10];
struct pos{
    int dir;
    int row;
    int col;
}poss[101];
struct pos res[101];
//入栈
void forward(int* row, int* col, int* type)
{
	//这里运用了二进制减少变量
    if (*type & 1)ch[*row][++ * col] = '@', * type ^= 1;
    else if (*type & 2)ch[++ * row][*col] = '@', * type ^= 2;
    else if (*type & 4)ch[*row][-- * col] = '@', * type ^= 4;
    else if (*type & 8)ch[-- * row][*col] = '@', * type ^= 8;
}
void print()
{
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            printf("%c ", ch[i][j]);
        }
        printf("\n");
    }
    return;
}
int judge(int row, int col,int tmp)
{
    int f = 0;
    poss[tmp].col = col;
    poss[tmp].row = row;
    if (col + 1 < 10 && ch[row][col + 1] == ' ')poss[tmp].dir += 1, f = 1;
    if (col - 1 >= 0 && ch[row][col - 1] == ' ')poss[tmp].dir += 4, f = 1;
    if (row + 1 < 10 && ch[row + 1][col] == ' ')poss[tmp].dir += 2, f = 1;
    if (row - 1 >= 0 && ch[row - 1][col] == ' ')poss[tmp].dir += 8, f = 1;
    return f;
}
int main()
{
    int startr, startc;
    int endr, endc;
    int min=0;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            scanf("%c%*c", &ch[i][j]);
            //起点
            if (ch[i][j] == '@') {
                startr = i; startc = j;
            }
            //终点
            else if (ch[i][j] == '*') {
                endr = i; endc = j;
                ch[i][j] = ' ';
            }
        }
    }
    system("cls");
    print();
    Sleep(500);
    int tmp = 0;
    while (1) {
        int f = judge(startr, startc, tmp);
        system("cls");
        forward(&startr, &startc, &poss[tmp].dir);
        print();
        Sleep(500);
        if (startr == endr && startc == endc) {
            //记录最短路
            if (min == 0) {
                min = tmp + 1;
                for (int k = 0; k < min; k++)res[k] = poss[k];
                res[min].row = endr;
                res[min].col = endc;
            }
            else if (min > tmp){
	            min = tmp+1;
	            for (int k = 0; k < min; k++)res[k] = poss[k];
                res[min].row = endr;
                res[min].col = endc;
            }
            ch[endr][endc] = ' ';
            while (poss[tmp].dir == 0 && tmp >= 0){ 
                ch[poss[tmp].row][poss[tmp].col] = ' ';
                tmp--;
                system("cls");
                print();
                Sleep(100);
            }
            if (tmp < 0) {
                //输出最短路
                for (int i = 0; i <= min; i++) {
			        ch[res[i].row][res[i].col] = '@';
			    }
			    system("cls");
			    print();
                printf("%d",min);
                return 0;
            }
            startr = poss[tmp].row;
            startc = poss[tmp].col;
            forward(&startr, &startc, &poss[tmp].dir);
            system("cls");
            print();
            Sleep(500);
        }
        else if (f == 0) {
        while (poss[tmp].dir == 0 && tmp >= 0){
            ch[poss[tmp].row][poss[tmp].col] = ' ';
            tmp--;
            system("cls");
            print();
            Sleep(100);
            }
            if (tmp < 0) {
	            //输出最短路
	            for (int i = 0; i <= min; i++) {
			        ch[res[i].row][res[i].col] = '@';
			    }
			    system("cls");
			    print();
                printf("%d",min);
                return 0;
            }
            startr = poss[tmp].row;
            startc = poss[tmp].col;
            forward(&startr, &startc, &poss[tmp].dir);
            system("cls");
            print();
            Sleep(500);
        }
        tmp++;
    }
}

输入实例

1
2
3
4
5
6
7
8
9
10
# # #   # #   # # #
# @               #
# #   # # # # #   #
#                 #
# #   # # #   #   #
# #   #   #   #   #
# #   #   #   #   #
# #       #   #   #
# # # # # #   #   #
# # # # # # * #   #

其实可以发现上面的很多代码都是重复的，主要是因为我们不是只要找到一条通向终点的路，而是要找到最短路，所以我们要将所有的路都走一遍。

计算机 > C语言
#算法学习
深度优先搜索-DFS
http://example.com/posts/深度优先搜索/
作者
晓寒
发布于
2022年11月13日
许可协议