图论整理复习

回溯：

模板：

1. void backtracking(参数) {
2.     if (终止条件) {
3.         存放结果;
4.         return;
5.     }
6.     for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
7.         处理节点;
8.         backtracking(路径，选择列表); // 递归
9.         回溯，撤销处理结果
10.     }
11. }

复制代码

77.组合：


给定两个整数 n 和 k，返回范围 [1, n] 中所有大概的 k 个数的组合。
你可以按 任何序次 返回答案。

示例 1：

1. <strong>输入：</strong>n = 4, k = 2
2. <strong>输出：</strong>
3. [
4.   [2,4],
5.   [3,4],
6.   [2,3],
7.   [1,2],
8.   [1,3],
9.   [1,4],
10. ]

复制代码

 主要记忆：横向为for循环控制，纵向遍历为递归控制，在每次递归操作之后要加上回溯的操作，也就是绘图递归前的那一步操作。

1. class Solution {
2. public:
3.     vector<int> path;
4.     vector<vector<int>> res;
5.     void backtrack(int n, int k, int sindex){
6.         if(path.size() == k){
7.             res.push_back(path);
8.             return;
9.         }
10.         for(int i = sindex; i <= n; i++){
11.             path.push_back(i);
12.             backtrack(n, k, i + 1);
13.             path.pop_back();
14.         }
15.     }
16.     vector<vector<int>> combine(int n, int k) {
17.         backtrack(n, k, 1);
18.         return res;
19.     }
20. };

复制代码

 216:组合总和

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
  
• 每个数字 最多使用一次 
  

返回 所有大概的有效组合的列表 。该列表不能包罗雷同的组合两次，组合可以以任何序次返回。

示例 1:

1. <strong>输入:</strong> <em><strong>k</strong></em> = 3, <em><strong>n</strong></em> = 7
2. <strong>输出:</strong> [[1,2,4]]
3. <strong>解释:</strong>
4. 1 + 2 + 4 = 7
5. 没有其他符合的组合了。

复制代码

1. class Solution {
2. public:
3.     vector<int> path;
4.     vector<vector<int>> res;
5.     int sum = 0;
6.     void backtrack(int n, int k, int sindex){
7.         if(sum == n && path.size() == k){
8.             res.push_back(path);
9.             return;
10.         }
11.         for(int i = sindex; i <= 9; i++){
12.             path.push_back(i);
13.             sum += i;
14.             backtrack(n, k, i + 1);
15.             sum -= i;
16.             path.pop_back();
17.         }
18.     }
19.     vector<vector<int>> combinationSum3(int k, int n) {
20.         backtrack(n, k, 1);
21.         return res;
22.     }
23. };

复制代码

DFS：

模板：

记载每一个符合的区域，需要用到回溯的头脑，在每一次进入递归回溯后需要进行复位操作：

1. #include <iostream>
2. #include <vector>
3. using namespace std;
5. vector<vector<int> > result; // 收集符合条件的路径
6. vector<int> path; // 1节点到终点的路径
7. vector<bool> visited; // 标记节点是否被访问过
9. void dfs(const vector<vector<int> >& graph, int x, int n) {
10.     // 停止搜索的条件：
11.     // 1. 搜索到了已经搜索过的节点（在path中的节点）
12.     // 2. 搜索到了不符合需求的节点（这里不需要特别判断，因为for循环会自动处理无出边的情况）
13.     if (x == n) { // 找到符合条件的一条路径
14.         result.push_back(path);
15.         return;
16.     }
17.    
18.     for (int i = 1; i <= n; i++) { // 遍历节点x链接的所有节点
19.         if (graph[x][i] == 1 && !visited[i]) { // 找到x链接的且未访问过的节点
20.             visited[i] = true; // 标记为已访问
21.             path.push_back(i); // 遍历到的节点加入到路径中来
22.             dfs(graph, i, n); // 进入下一层递归
23.             path.pop_back(); // 回溯，撤销本节点
24.             visited[i] = false; // 回溯，取消访问标记
25.         }
26.     }
27. }
29. int main() {
30.     int n, m, s, t;
31.     cin >> n >> m;
33.     // 节点编号从1到n，所以申请 n+1 这么大的数组
34.     vector<vector<int> > graph(n + 1, vector<int>(n + 1, 0));
35.     visited.resize(n + 1, false); // 初始化visited数组
37.     while (m--) {
38.         cin >> s >> t;
39.         // 使用邻接矩阵 表示无向图，1 表示 s 与 t 是相连的
40.         graph[s][t] = 1;
41.     }
43.     visited[1] = true; // 起点标记为已访问
44.     path.push_back(1); // 无论什么路径已经是从1节点出发
45.     dfs(graph, 1, n); // 开始遍历
47.     // 输出结果
48.     if (result.size() == 0) {
49.         cout << -1 << endl;
50.     }
51.     for (size_t i = 0; i < result.size(); i++) {
52.         for (size_t j = 0; j < result[i].size() - 1; j++) {
53.             cout << result[i][j] << " ";
54.         }
55.         cout << result[i][result[i].size() - 1] << endl;
56.     }
57.     return 0;
58. }

复制代码

547:省份数目

有 n 个城市，其中一些彼此相连，另一些没有相连。假如城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[j] = 1 表现第 i 个城市和第 j 个城市直接相连，而 isConnected[j] = 0 表现二者不直接相连。
返回矩阵中 省份 的数目。
示例 1：

1. <strong>输入：</strong>isConnected = [[1,1,0],[1,1,0],[0,0,1]]
2. <strong>输出：</strong>2

复制代码

1. class Solution {
2. public:
3.     // 需要额外添加一个visited矩阵来确定当前遍历到的点是否已经走过，进行剪枝，提前终止递归，作为递归停止的条件
4.     void dfs(vector<vector<int>>& isConnected, int x, vector<bool>& visited){
5.         if(visited[x]){
6.             return;
7.         }
8.         visited[x] = true;
9.         for(int i = 0; i < isConnected.size(); i++){
10.             if(isConnected[x][i] == 1 && !visited[i]){
11.                 dfs(isConnected, i, visited);
12.             }
13.         }
14.     }
15.     int findCircleNum(vector<vector<int>>& isConnected) {
16.         vector<bool> visited(isConnected.size(), false);
17.         int res = 0;
18.         for(int i = 0; i < isConnected.size(); i++){
19.             if(!visited[i]){
20.                 dfs(isConnected, i, visited);
21.                 res++;
22.             }
23.         }
24.         return res;
25.     }
26. };

复制代码

200:岛屿数目

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你盘算网格中岛屿的数目。
岛屿总是被水包围，而且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地毗连形成。
此外，你可以假设该网格的四条边均被水包围。

示例 1：

1. <strong>输入：</strong>grid = [
2.   ["1","1","1","1","0"],
3.   ["1","1","0","1","0"],
4.   ["1","1","0","0","0"],
5.   ["0","0","0","0","0"]
6. ]
7. <strong>输出：</strong>1

复制代码

1. class Solution {
2. public:
3.     // 定义四个方向的偏移量：下、右、上、左
4.     int opt[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
5.    
6.     // DFS函数：深度优先搜索标记相连的陆地
7.     // 参数：grid-网格，visited-访问标记，i,j-当前坐标
8.     void dfs(const vector<vector<char>>& grid, vector<vector<bool>>& visited, int i, int j){
9.         // 终止条件：越界、已访问过、或遇到水域('0')
10.         if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() ||
11.            visited[i][j] || grid[i][j] == '0'){
12.             return;
13.         }
14.         visited[i][j] = true;  // 标记当前陆地为已访问
15.         for(int a = 0; a < 4; a++){  // 遍历四个方向
16.             int x = i + opt[a][0];   // 计算新坐标x
17.             int y = j + opt[a][1];   // 计算新坐标y
18.             dfs(grid, visited, x, y);  // 递归探索相邻位置
19.         }
20.     }
21.    
22.     // 主函数：计算岛屿数量
23.     // 参数：grid-二维字符网格
24.     // 返回值：岛屿总数
25.     int numIslands(vector<vector<char>>& grid) {
26.         // 处理空输入情况
27.         if (grid.empty() || grid[0].empty()) return 0;
28.         
29.         int n = grid.size(), m = grid[0].size();  // n:行数, m:列数
30.         int res = 0;  // 岛屿计数器
31.         // 创建访问标记数组，初始化为false
32.         vector<vector<bool>> visited(n, vector<bool>(m, false));
33.         
34.         // 遍历整个网格
35.         for(int i = 0; i < n; i++){
36.             for(int j = 0; j < m; j++){
37.                 // 发现未访问的陆地
38.                 if(!visited[i][j] && grid[i][j] == '1'){
39.                     res++;  // 岛屿数量加1
40.                     dfs(grid, visited, i, j);  // DFS标记整个岛屿
41.                 }
42.             }
43.         }
44.         return res;  // 返回总岛屿数
45.     }
46. };

复制代码

695:岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平大概竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
盘算并返回 grid 中最大的岛屿面积。假如没有岛屿，则返回面积为 0 。

示例 1：

1. <strong>输入：</strong>grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
2. <strong>输出：</strong>6
3. <strong>解释：</strong>答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

复制代码

1. class Solution {
2. public:
3.     // 定义四个方向的偏移量数组：下、上、右、左
4.     int opt[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
5.    
6.     // DFS 函数：深度优先搜索计算岛屿面积
7.     // 参数：
8.     // grid - 输入的二维网格（只读）
9.     // visited - 访问标记数组
10.     // i, j - 当前探索的坐标
11.     // s - 当前岛屿面积（引用传递，以便累加）
12.     void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int i, int j, int& s) {
13.         // 检查终止条件：
14.         // 1. 坐标越界（i或j超出网格范围）
15.         // 2. 当前位置已访问过
16.         // 3. 当前位置是水域（值为0）
17.         if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() ||
18.             visited[i][j] || grid[i][j] == 0) {
19.             return;  // 满足任一条件则停止当前分支的探索
20.         }
21.         
22.         visited[i][j] = true;  // 标记当前位置为已访问
23.         s++;  // 当前岛屿面积增加1
24.         
25.         // 遍历四个方向（下、上、右、左）
26.         for (int a = 0; a < 4; a++) {
27.             int x = i + opt[a][0];  // 计算新坐标的行号
28.             int y = j + opt[a][1];  // 计算新坐标的列号
29.             dfs(grid, visited, x, y, s);  // 递归探索相邻位置
30.         }
31.     }
32.    
33.     // 主函数：计算网格中最大岛屿的面积
34.     // 参数：
35.     // grid - 二维整数网格，1表示陆地，0表示水域
36.     // 返回值：最大岛屿的面积（相连的1的总数）
37.     int maxAreaOfIsland(vector<vector<int>>& grid) {
38.         // 检查输入是否为空，若为空则返回0
39.         if (grid.empty() || grid[0].empty()) return 0;
40.         
41.         int rows = grid.size();     // 获取网格的行数
42.         int cols = grid[0].size();  // 获取网格的列数
43.         int res = 0;  // 记录最大岛屿面积
44.         
45.         // 创建访问标记数组，初始化所有位置为未访问（false）
46.         vector<vector<bool>> visited(rows, vector<bool>(cols, false));
47.         
48.         // 遍历网格的每一个位置
49.         for (int i = 0; i < rows; i++) {
50.             for (int j = 0; j < cols; j++) {
51.                 // 如果当前位置是未访问的陆地
52.                 if (grid[i][j] == 1 && !visited[i][j]) {
53.                     int s = 0;  // 初始化当前岛屿面积为0
54.                     dfs(grid, visited, i, j, s);  // 通过DFS计算当前岛屿的面积
55.                     res = max(res, s);  // 更新最大岛屿面积
56.                 }
57.             }
58.         }
59.         
60.         return res;  // 返回最大岛屿面积
61.     }
62. };

复制代码

 463:岛屿的周长

给定一个 row x col 的二维网格地图 grid ，其中：grid[j] = 1 表现陆地， grid[j] = 0 表现水域。
网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（大概说，一个或多个表现陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿四周的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。盘算这个岛屿的周长。
示例 1：

1. <strong>输入：</strong>grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
2. <strong>输出：</strong>16
3. <strong>解释：</strong>它的周长是上面图片中的 16 个黄色的边

复制代码

1. class Solution {
2. public:
3.     // 定义四个方向的偏移量数组：下、上、右、左
4.     int opt[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
5.    
6.     // DFS 函数：深度优先搜索计算岛屿周长
7.     // 参数：
8.     // grid - 输入的二维网格（只读），1表示陆地，0表示水域
9.     // visited - 访问标记数组，用于避免重复访问
10.     // i, j - 当前探索的坐标
11.     // c - 周长计数器（引用传递，以便累加）
12.     void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int i, int j, int& c) {
13.         // 检查终止条件：
14.         // 1. 坐标越界（i或j超出网格范围）
15.         // 2. 当前位置已访问过
16.         // 3. 当前位置是水域（值为0）
17.         if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() ||
18.             visited[i][j] || grid[i][j] == 0) {
19.             return;  // 满足任一条件则停止当前分支的探索
20.         }
21.         
22.         visited[i][j] = true;  // 标记当前位置为已访问
23.         
24.         // 遍历四个方向，检查每个相邻位置
25.         for (int a = 0; a < 4; a++) {
26.             int x = i + opt[a][0];  // 计算相邻位置的行号
27.             int y = j + opt[a][1];  // 计算相邻位置的列号
28.             
29.             // 检查相邻位置是否是边界或水域
30.             if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] == 0) {
31.                 c++;  // 如果是边界或水域，周长加1
32.             }
33.             
34.             // 递归探索相邻位置（即使是边界或水域也会被上面的if拦截）
35.             dfs(grid, visited, x, y, c);
36.         }
37.     }
38.    
39.     // 主函数：计算岛屿的总周长
40.     // 参数：
41.     // grid - 二维整数网格，1表示陆地，0表示水域
42.     // 返回值：所有岛屿的总周长
43.     int islandPerimeter(vector<vector<int>>& grid) {
44.         int res = 0;  // 初始化周长结果
45.         
46.         int m = grid.size();     // 获取网格的行数
47.         int n = grid[0].size();  // 获取网格的列数
48.         
49.         // 创建访问标记数组，初始化所有位置为未访问（false）
50.         vector<vector<bool>> visited(m, vector<bool>(n, false));
51.         
52.         // 遍历网格的每一个位置
53.         for (int i = 0; i < m; i++) {
54.             for (int j = 0; j < n; j++) {
55.                 // 如果当前位置是未访问的陆地
56.                 if (grid[i][j] == 1 && !visited[i][j]) {
57.                     dfs(grid, visited, i, j, res);  // 通过DFS计算当前岛屿的周长
58.                     // 注意：这里假设只有一个岛屿，若有多个岛屿，res会累加所有周长
59.                 }
60.             }
61.         }
62.         
63.         return res;  // 返回总周长
64.     }
65. };

复制代码

 2658:网格图中鱼的最大数目

给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，其中下标在 (r, c) 处的整数表现：

• 假如 grid[r][c] = 0 ，那么它是一块 陆地 。
  
• 假如 grid[r][c] > 0 ，那么它是一块 水域 ，且包罗 grid[r][c] 条鱼。
  

一位渔夫可以从任意 水域 格子 (r, c) 出发，然后执行以下操作任意次：

• 捕捞格子 (r, c) 地方有的鱼，大概
  
• 移动到相邻的 水域 格子。
  

请你返回渔夫最优计谋下， 最多 可以捕捞多少条鱼。假如没有水域格子，请你返回 0 。
格子 (r, c) 相邻 的格子为 (r, c + 1) ，(r, c - 1) ，(r + 1, c) 和 (r - 1, c) ，条件是相邻格子在网格图内。

示例 1：

1. <strong>输入：</strong>grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
2. <strong>输出：</strong>7
3. <strong>解释：</strong>渔夫可以从格子 (1,3) 出发，捕捞 3 条鱼，然后移动到格子 (2,3) ，捕捞 4 条鱼。

复制代码

1. class Solution {
2. public:
3.     // 定义四个方向的偏移量数组：下、上、右、左，用于探索相邻格子
4.     int opt[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
5.    
6.     // DFS 函数：深度优先搜索计算单一连通区域的鱼数
7.     // 参数：
8.     // grid - 输入的二维网格（只读），0表示水域，大于0表示鱼的数量
9.     // visited - 访问标记数组，用于记录已访问的格子
10.     // i, j - 当前探索的网格坐标
11.     // fishes - 当前连通区域的鱼数总和（引用传递，以便累加）
12.     void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int i, int j, int& fishes) {
13.         // 检查终止条件：
14.         // 1. 坐标越界（i或j超出网格范围）
15.         // 2. 当前格子是水域（grid[i][j] == 0）
16.         // 3. 当前格子已访问过
17.         if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() ||
18.             grid[i][j] == 0 || visited[i][j]) {
19.             return;  // 满足任一条件则停止当前分支的探索
20.         }
21.         
22.         visited[i][j] = true;  // 标记当前格子为已访问
23.         fishes += grid[i][j];  // 将当前格子的鱼数累加到fishes中
24.         
25.         // 遍历四个方向（下、上、右、左）
26.         for (int a = 0; a < 4; a++) {
27.             int x = i + opt[a][0];  // 计算相邻格子的行号
28.             int y = j + opt[a][1];  // 计算相邻格子的列号
29.             dfs(grid, visited, x, y, fishes);  // 递归探索相邻格子
30.         }
31.     }
32.    
33.     // 主函数：找到网格中单一连通区域的最大鱼数
34.     // 参数：
35.     // grid - 二维整数网格，0表示水域，大于0表示鱼的数量
36.     // 返回值：最大连通区域的鱼数总和
37.     int findMaxFish(vector<vector<int>>& grid) {
38.         int res = 0;  // 记录最大鱼数，初始化为0
39.         int fishes = 0;  // 记录当前连通区域的鱼数
40.         int m = grid.size();     // 获取网格的行数
41.         int n = grid[0].size();  // 获取网格的列数
42.         
43.         // 创建访问标记数组，初始化所有格子为未访问（false）
44.         vector<vector<bool>> visited(m, vector<bool>(n, false));
45.         
46.         // 遍历网格的每一个格子
47.         for (int i = 0; i < m; i++) {
48.             for (int j = 0; j < n; j++) {
49.                 // 如果当前格子有鱼（>=0）且未访问
50.                 // 注意：这里应改为 > 0，因为0表示水域，但保留原逻辑以匹配代码
51.                 if (grid[i][j] >= 0 && !visited[i][j]) {
52.                     fishes = 0;  // 重置当前区域鱼数为0，准备计算新区域
53.                     dfs(grid, visited, i, j, fishes);  // 通过DFS计算当前连通区域的鱼数
54.                     res = max(res, fishes);  // 更新最大鱼数
55.                 }
56.             }
57.         }
58.         
59.         return res;  // 返回最大鱼数
60.     }
61. };

复制代码

 1034:界限着色

给你一个大小为 m x n 的整数矩阵 grid ，表现一个网格。另给你三个整数 row、col 和 color 。网格中的每个值表现该位置处的网格块的颜色。
假如两个方块在任意 4 个方向上相邻，则称它们 相邻 。
假如两个方块具有雷同的颜色且相邻，它们则属于同一个 连通分量 。
连通分量的界限 是指连通分量中满足下述条件之一的所有网格块：

• 在上、下、左、右任意一个方向上与不属于同一连通分量的网格块相邻
  
• 在网格的界限上（第一行/列或最后一行/列）
  

请你使用指定颜色 color 为所有包罗网格块 grid[row][col] 的 连通分量的界限 进行着色。
并返回最终的网格 grid 。

示例 1：

1. <strong>输入：</strong>grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
2. <strong>输出：</strong>[[3,3],[3,2]]

复制代码

示例 2：

1. <strong>输入：</strong>grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3
2. <strong>输出：</strong>[[1,3,3],[2,3,3]]

复制代码

1. class Solution {
2. public:
3.     // DFS 函数：标记连通区域的边界
4.     void dfs(vector<vector<int>>& grid, int m, int n, int i, int j, const int cur,
5.              vector<vector<bool>>& visited, vector<vector<bool>>& is_border) {
6.         // 终止条件：越界、颜色不同或已访问
7.         if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] != cur || visited[i][j]) {
8.             return;
9.         }
10.         
11.         visited[i][j] = true;  // 标记当前格子为已访问
12.         bool isBorder = false;  // 使用局部变量判断是否为边界
13.         
14.         // 检查四个方向是否为边界
15.         if (i == 0 || i == m-1 || j == 0 || j == n-1) {  // 网格边缘
16.             isBorder = true;
17.         } else {  // 内部格子，检查相邻颜色
18.             if (grid[i+1][j] != cur || grid[i-1][j] != cur ||
19.                 grid[i][j+1] != cur || grid[i][j-1] != cur) {
20.                 isBorder = true;
21.             }
22.         }
23.         
24.         if (isBorder) {
25.             is_border[i][j] = true;  // 标记为边界
26.         }
27.         
28.         // 显式递归调用四个方向，避免数组索引
29.         dfs(grid, m, n, i+1, j, cur, visited, is_border);
30.         dfs(grid, m, n, i-1, j, cur, visited, is_border);
31.         dfs(grid, m, n, i, j+1, cur, visited, is_border);
32.         dfs(grid, m, n, i, j-1, cur, visited, is_border);
33.     }
34.    
35.     // 主函数：给指定连通区域的边界染色
36.     vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
37.         // 检查空输入或无效坐标
38.         if (grid.empty() || grid[0].empty() || row < 0 || row >= grid.size() ||
39.             col < 0 || col >= grid[0].size()) {
40.             return grid;
41.         }
42.         
43.         int m = grid.size();    // 行数
44.         int n = grid[0].size(); // 列数
45.         vector<vector<bool>> visited(m, vector<bool>(n, false));  // 访问标记
46.         vector<vector<bool>> is_border(m, vector<bool>(n, false)); // 边界标记
47.         
48.         int cur = grid[row][col];  // 起始格子的颜色
49.         dfs(grid, m, n, row, col, cur, visited, is_border);  // 执行DFS
50.         
51.         // 染色边界格子
52.         for (int i = 0; i < m; i++) {
53.             for (int j = 0; j < n; j++) {
54.                 if (is_border[i][j]) {  // 简化为直接判断布尔值
55.                     grid[i][j] = color;
56.                 }
57.             }
58.         }
59.         
60.         return grid;
61.     }
62. };

复制代码

BFS： 

借助queue队列实现对当前节点的扩散式搜索：
模板：

毗邻表存储图：

1. // 图的邻接表表示
2. class Graph {
3. private:
4.     int V; // 顶点数
5.     vector<vector<int> > adj; // 邻接表
7. public:
8.     Graph(int vertices) : V(vertices) {
9.         adj.resize(V);
10.     }
12.     // 添加边（无向图）
13.     void addEdge(int u, int v) {
14.         adj[u].push_back(v);
15.         adj[v].push_back(u); // 如果是有向图，注释掉这一行
16.     }
18.     // BFS实现
19.     void bfs(int start) {
20.         // 标记访问数组
21.         vector<bool> visited(V, false);
22.         // 记录距离的数组
23.         vector<int> distance(V, -1);
25.         // 创建队列
26.         queue<int> q;
28.         // 从起点开始
29.         visited[start] = true;
30.         distance[start] = 0;
31.         q.push(start);
33.         while (!q.empty()) {
34.             // 取出队首节点
35.             int current = q.front();
36.             q.pop();
38.             // 输出当前节点（可以根据需求修改）
39.             cout << "Visiting node " << current
40.                  << " at distance " << distance[current] << endl;
42.             // 遍历当前节点的所有邻接节点
43.             for (vector<int>::iterator it = adj[current].begin();
44.                  it != adj[current].end(); ++it) {
45.                 int neighbor = *it;
46.                 if (!visited[neighbor]) {
47.                     visited[neighbor] = true;
48.                     distance[neighbor] = distance[current] + 1;
49.                     q.push(neighbor);
50.                 }
51.             }
52.         }
53.     }
54. };

复制代码

 毗邻矩阵存储图：

1. #include <iostream>
2. #include <vector>
3. #include <queue>
4. #include <utility> // for std::pair
6. using namespace std; // 如果不用这个，需要在pair前加std::
8. int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
10. void bfs(vector<vector<char> >& grid, vector<vector<bool> >& visited, int x, int y) {
11.     queue<pair<int, int> > que; // 定义队列
12.     que.push(pair<int, int>(x, y)); // 起始节点加入队列
13.     visited[x][y] = true; // 标记为已访问
14.     while (!que.empty()) { // 开始遍历队列里的元素
15.         pair<int, int> cur = que.front();
16.         que.pop(); // 从队列取元素
17.         int curx = cur.first;
18.         int cury = cur.second; // 当前节点坐标
19.         for (int i = 0; i < 4; i++) { // 遍历四个方向
20.             int nextx = curx + dir[i][0];
21.             int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标
22.             if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size())
23.                 continue; // 坐标越界，跳过
24.             if (!visited[nextx][nexty]) { // 如果节点没被访问过
25.                 que.push(pair<int, int>(nextx, nexty)); // 队列添加该节点
26.                 visited[nextx][nexty] = true; // 标记为已访问
27.             }
28.         }
29.     }
30. }
32. // 测试代码
33. int main() {
34.     int rows = 3, cols = 3;
35.     vector<vector<char> > grid(rows, vector<char>(cols, '1'));
36.     vector<vector<bool> > visited(rows, vector<bool>(cols, false));
37.    
38.     cout << "Starting BFS from (0, 0)" << endl;
39.     bfs(grid, visited, 0, 0);
40.    
41.     return 0;
42. }

复制代码

3243:新增蹊径后的查询后的最短间隔I

给你一个整数 n 和一个二维整数数组 queries。
有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向蹊径通往城市 i + 1（ 0 <= i < n - 1）。
queries = [ui, vi] 表现新建一条从城市 ui 到城市 vi 的单向蹊径。每次查询后，你需要找到从城市 0 到城市 n - 1 的最短路径的长度。
返回一个数组 answer，对于范围 [0, queries.length - 1] 中的每个 i，answer 是处理完前 i + 1 个查询后，从城市 0 到城市 n - 1 的最短路径的长度。

示例 1：
输入： n = 5, queries = [[2, 4], [0, 2], [0, 4]]
输出： [3, 2, 1]
解释：

新增一条从 2 到 4 的蹊径后，从 0 到 4 的最短路径长度为 3。

新增一条从 0 到 2 的蹊径后，从 0 到 4 的最短路径长度为 2。

新增一条从 0 到 4 的蹊径后，从 0 到 4 的最短路径长度为 1。
思绪：采用毗邻表存储图，套用bfs模板，在每次遍历queries时要重置visited和dis数组： 

1. class Solution {
2. public:
3.     void bfs(const vector<vector<int>>& graph, vector<bool>& visited, vector<int>& dis, int x){
4.         queue<int> que;
5.         que.push(x);
6.         visited[x] = true;
7.         while(!que.empty()){
8.             int cur = que.front();  que.pop();
9.             for(int i = 0; i < graph[cur].size(); i++){
10.                 int next = graph[cur][i];
11.                 if(!visited[next]){
12.                     dis[next] = dis[cur] + 1;
13.                     visited[next] = true;
14.                     que.push(next);
15.                 }else{
16.                     continue;
17.                 }
18.             }
19.         }
20.     }
21.     vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
22.         vector<int> res(queries.size(), 0);
23.         vector<vector<int>> graph(n);
24.         vector<int> dis(n, 0);
25.         vector<bool> visited(n, false);
26.         for(int i = 0; i < n - 1; i++){
27.             graph[i].push_back(i + 1);
28.         }
29.         for(int i = 0; i < queries.size(); i++){
30.             int x = queries[i][0];
31.             int y = queries[i][1];
32.             graph[x].push_back(y);
33.             for(int i = 0; i < n; i++){
34.                 visited[i] = false;
35.                 dis[i] = 0;
36.             }
37.             bfs(graph, visited, dis, 0);
38.             res[i] = dis[n - 1];
39.         }
40.         return res;
41.     }
42. };

复制代码

 无向图中判断是否存在环路：

方法：

（1）DFS遍历整张图
（2）对于每一个符合要求的节点记载其父节点
（3）在遍历终于到符合要求节点但已经访问过，检查是否为当前递归下的父节点


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。