DFS和BFS简述_dfs与bfs

---

前言

本文将从特别简单的例题对DFS，BFS写法进行介绍和剖析

---

一、DFS与BFS

深度优先遍历（Depth First Search, 简称 DFS） 与广度优先遍历（Breath First Search）是图论中两种非常重要的算法。
因为树是特殊的图（连通无环图），所以本文基于图来讲解。

DFS

深度优先遍历主要思路是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。¹

通俗的讲，就和我们平时走迷宫一样只要找到一种可以走出去的办法我们就结束了
所以对于DFS来说并不能用来解决最短路问题，因为如果数据量一旦过大，递归树会越来越大最终导致爆栈。
对于DFS而言，只要有解即可。

BFS

广度优先遍历，指的是从图的一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点。放到树的遍历中而言，就是层序遍历(levelorder)。
因为需要保存相邻节点，所以我们需要使用到队列(queue)这个数据结构，由于其具有先入先出的特性，就可以遍历完一层又遍历下一层。

---

例子

DFS代码一般为：

1. 递归出口
2. 标记当前位置
3. 递归找下一个单词
4. 回溯(将之前标记的位置还原)

BFS代码一般为

1. 初始状态入队
2. 只要队列不为空
   2.1 取队头元素
   2.2 扩展队列

n-皇后问题²

问题描述

n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数n，请你输出所有的满足条件的棋子摆法

测试案例

输入格式
共一行，包含整数 n。
输出格式
每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后，输出一个空行。
注意：行末不能有多余空格。
输出方案的顺序任意，只要不重复且没有遗漏即可。
数据范围
1≤n≤9
输入样例：
4
输出样例：

.Q…
…Q
Q…
…Q.

…Q.
Q…
…Q
.Q…

代码如下（示例）：

对于DFS代码的编写
一般都是
1.递归出口
2.标记当前位置
3.递归下一位置
4.回溯

#include <iostream>

using namespace std;

const int N = 20;
char map[N][N];
/* st[N}表示当前使用的行数，即皇后所在行。即横
*  dg[N]表示对角线
*  udg[N]表示反对角线
*/
bool st[N], dg[N], udg[N];
int n;

void dfs(int u) {
	//递归出口
    if (u == n) {
        for (int i = 0; i < n; i++) puts(map[i]);
        puts("");
        return ;
    }
    for (int i = 0; i < n; i++) {
    	//对角线 y = -x + b 反对角线 y = x + b
    	//故b = y + x  b = y - x这边 + n是为了防止为负数
        if (!st[i] && !dg[u + i] && !udg[n + i - u]) {
        	//标记当前位置
            map[u][i] = 'Q';
            st[i] = dg[u + i] = udg[n + i - u] = true;
            //递归下一个皇后
            dfs(u + 1);
            //回溯
            st[i] = dg[u + i] = udg[n + i - u] = false;
            map[u][i] = '.';
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++)
            map[i][j] = '.';
    dfs(0);
    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
36
37
38
39
40
41
42
43
44

---

矩阵中的路径³

问题描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

示例 1：

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出：true
示例 2：

输入：board = [[“a”,“b”],[“c”,“d”]], word = “abcd”
输出：false

思路

还是使用DFS
循环遍历数组，当找到第一个单词是即进行递归

1. 递归出口：当前单词为给出单词最后一个
2. 标记当前位置
3. 递归找下一个单词
4. 回溯(将之前标记的位置还原)

代码如下（示例）：

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (dfs(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }
private:
    bool dfs(vector<vector<char>>& board, string &word, int x, int y, int k) {
        //递归出口
        if (x >= board.size() || y >= board[0].size() || x < 0 || y < 0 || board[x][y] != word[k])
            return false;
        if (k == word.size() - 1) 
            return true;
        //标记位置
        char tmp = board[x][y];
        board[x][y] = '\0';
		//递归
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        for (int i = 0; i < 4; i++) {
            int sx = x + dx[i], sy = y + dy[i];
            if (dfs(board, word, sx, sy, k + 1)) return true;
        }
        //回溯用
        board[x][y] = tmp;
        return false;
    }
};
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

---

走迷宫问题⁴

问题描述

给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。
从(0, 0) 到(n - 1, m - 1)中最短路径为：
输入样例：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：
8

这里涉及到了要向上下左右移动的问题
这里我们定义两个数组，代表上右下左

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
1

思路

先将初始状态即(0, 0)入队
之后扩展看是否能走，且不能往回走所以需要有一个记录状态的数组st
最后返回答案即可。
代码如下

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
//使用pair来存储当前的位置
typedef pair<int, int> PII;

const int N = 110;
int map[N][N], dp[N][N];
int n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int bfs()
{
    queue<PII> q;
    //初始状态入队
    q.push({0, 0});
    memset(dp, -1, sizeof(dp));

    dp[0][0] = 0;

    while (!q.empty())
    {
        PII t = q.front();//取队头元素

        q.pop();//出队

        for (int i = 0; i < 4; i++)
        {
            int sx = t.first + dx[i], sy = t.second + dy[i];
            //扩展节点
            //边界， 前方能走， 没有走过
            if (sx >= 0 && sx < n && sy >= 0 && sy < m && map[sx][sy] == 0 && dp[sx][sy] == -1)
            {
                dp[sx][sy] = dp[t.first][t.second] + 1;//当前点到起点的距离
                q.push({sx, sy});//将新坐标入队
            }
        }
    }

    return dp[n - 1][m -1];
}
//使用dfs方法来实现
void dfs(int x, int y) {
    if (x == n - 1 && y == m - 1) {
        return;
    }
    for (int i = 0; i < 4; i++) {
        int sx = x + dx[i], sy = y + dy[i];
        if (sx < 0 || sy < 0 || sx >= n || sy >= m || map[sx][sy] == 1) continue;
        if (dp[sx][sy] > dp[x][y] + 1){
            dp[sx][sy] = dp[x][y] + 1;
            dfs(sx, sy);
        }
    }
    return ;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &map[i][j]);
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    dfs(0,0);
    printf("%d", dp[n - 1][m - 1]);
    cout << bfs() << endl;
    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
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

当然在这里也可以用dfs来实现，但是由于dfs很容易对同一个位置重复遍历这样很容易超时，甚至程序死循环。
在这里使用if (dp[sx][sy] > dp[x][y] + 1)来判断，如果现在的节点是比之前遍历的大，才继续遍历（其实就是避免了重复访问）。

---

总结

DFS

DFS代码一般为重点为找对递归出口防止无限递归

1. 递归出口
2. 标记当前位置
3. 递归找下一个单词
4. 回溯(将之前标记的位置还原)

BFS

BFS代码不能用于求权值不同的最短路问题，只能用来求权值相同的最短路问题。

1. 初始状态入队
2. 只要队列不为空
   2.1 取队头元素
   2.2 扩展队列

虽然可以使用bfs的代码肯定可以用dfs来实现，但是由于dfs很容易重复访问（回溯），导致递归树巨大导致超时，依实际情况而定
上面的为dfs
下面的为bfs
效率一看便知

持续更新中…

---

1. 出自https://blog.csdn.net/weixin_41385912/article/details/105549124 ↩︎

2. 出自acwing出自acwing ↩︎

3. 剑指offer 12: leetcode. ↩︎

4. 走迷宫问题:acwing844 ↩︎