代码随想录Day66 | 图的DFS与BFS

DFS

文档讲解：代码随想录
视频讲解：
状态

本质上就是回溯算法。

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

    for (选择：本节点所连接的其他节点) {
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

797.所有可能的路径

文档讲解：代码随想录
视频讲解：
状态

dfs搜索路径即可。
终止条件为当当前搜索点的下标为n-1时。

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;
public:
    void dfs(int index,vector<vector<int>>& graph)
    {
        if(index == graph.size()-1)
        {
            res.push_back(path);
            return;
        }
        for(auto& i : graph[index])
        {
            path.push_back(i);
            dfs(i,graph);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        path.push_back(0);
        dfs(0,graph);
        return res;
    }
};
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

无向图和有向图的处理

无向图在dfs的时候需要考虑后续节点的连通会与父节点连接，所以，dfs参数中需要加上一个父节点

void dfs(int n,int fa)
{
	for(int y : graph[n])
	{
		if(y != fa)
		{
			dfs();
		}
	}
}
1
2
3
4
5
6
7
8
9
10

BFS

文档讲解：代码随想录
视频讲解：
状态

从出发点一圈一圈的搜索，需要使用数据结构来存储遍历的数据，可以是有队列或者栈。
以队列为例

//定义移动方向，只能上下左右， 不能对角线移动
vector<int> dir = {0,1,1,0,-1,0,0,-1}
// grid 是地图，也就是一个二维数组
// visited标记访问过的节点，不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
    queue<pair<int, int>> que; // 定义队列
    que.push({x, y}); // 起始节点加入队列
    visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点
    while(!que.empty()) { // 开始遍历队列里的元素
        pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素
        int curx = cur.first;
        int cury = cur.second; // 当前节点坐标
        for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历
            int nextx = curx + dir[i][0];
            int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 坐标越界了，直接跳过
            if (!visited[nextx][nexty]) { // 如果节点没被访问过
                que.push({nextx, nexty});  // 队列添加该节点为下一轮要遍历的节点
                visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

一定要注意当点加入队列就需要立刻标记，否则会重复访问

200.岛屿数量

本题可以很好的练习了解BFS

class Solution {
private:
    //搜寻方向 上下左右
    int dir[4][2] = {0,1,1,0,-1,0,0,-1};
public:
    //bfs
    //grid 地图
    //visited 记录访问过的节点
    //x,y遍历起点坐标
    void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y)
    {
        //队列
        queue<pair<int,int>> que;
        que.push({x,y});
        visited[x][y] = true;

        //开始BFS
        while(!que.empty())
        {
            pair<int,int> cur = que.front();
            que.pop();
            int curx = cur.first;
            int cury = cur.second;
            for(int i=0;i<4;i++)
            {
                int nextx = curx + dir[i][0];
                int nexty = cury + dir[i][1];
                if(nextx <0 || nextx >= grid.size() || nexty<0 || nexty >= grid[0].size()) continue;
                if(!visited[nextx][nexty] && grid[nextx][nexty] == '1')
                {
                    que.push({nextx,nexty});
                    visited[nextx][nexty] = true;
                }
            }
        }
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<bool>> visited = vector<vector<bool>>(n,vector<bool>(m,false));
        int res = 0;
        //对每个岛屿进行遍历搜寻四周岛屿
        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<m;j++)
            {
                if(!visited[i][j] && grid[i][j] == '1')
                {
                    res++;
                    bfs(grid,visited,i,j);
                }
            }
        }
        return res;
    }
};
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