经典算法模版

图论 – 遍历篇

By crabboss

图论的题目目前分为5种：

  • 1 图遍历 – dfs或者bfs为主
  • 2 并查集 – 查询某两个节点是否存在同一集合
  • 3 拓扑排序
  • 4 最小生成树 – Prim, Kruskal
  • 5 最短路径
    • 单源最短路径 – Dijkstra，Bell_ford
    • 多源最短路径 – Folyd

1 图遍历模版

今天我们关注图的遍历，从遍历模板中我们已经得到了图该如何进行遍历，此处我们再复习一下：

1.1 DFS

int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

void DFS(vector& grid, vector& visited, int x, int y){
	if (visited[x][y] || grid[x][y] == '0') return ;
	visited[x][y] = true;
	for(int i=0; i<4; i++){
		int next_x = x + dir[i][0];
		int next_y = y + dir[i][1];
		if (next_x < 0 || next_x > grid.size()) || next_y < 0 || next_y > grid[0].size()) continue;
		DFS(grid, visited, next_x, next_y);
	}
}

1.2 BFS

int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

void BFS(vector>& grid, vector>& visited, int x, int y){
	queue> que;
	que.push({x, y});
	visited[x][y] = true;
	while(!que.empty()){
		for(int i=0; i<4; i++){
			pair node = que.front(); que.pop();
			int next_x = x + node.first;
			int next_y = y + node.second;
			if (next_x < 0 || next_x > grid.size() || next_y < 0 || next_y > grid[0].size()) continue;
			if (grid[next_x][next_y] != '0' && !visited[next_x][next_y]){
				que.push({next_x, next_y});
				visited[next_x][next_y];
			}
		}
	}
}

2 真题演练

2.1 岛屿数量

解题思路：

  • 1 利用图遍历将同一块岛屿内的陆地全部访问。
  • 2 图遍历需要注意的问题：
    • 入口中返回条件：已经被访问过了或者不在岛屿中。
    • 上下探索条件：不能访问岛屿的边界之外。
2.2.1 DFS版本
#include <iostream>
#include <vector>
using namespace std;

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){
    if (visited[x][y] == true || grid[x][y] == 0) return ;
    visited[x][y] = true;
    for(int i=0; i < 4; i++){
        int next_x = x + dir[i][0];
        int next_y = y + dir[i][1];
        if (next_x < 0 || next_y < 0 || next_x >= grid.size() || next_y >= grid[0].size()) continue;
        dfs(grid, visited, next_x, next_y);
    }
}

int main(){
    // 1 处理输入
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    int x;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> x;
            if (x) grid[i][j] = 1;
        }
    }
    // 2 处理岛屿数量
    int result = 0;
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if (visited[i][j] == false && grid[i][j] == 1){
                result++;
                dfs(grid, visited, i, j);
            }
        }
    }
    // 3 打印结果
    cout << result;
    return 0;
}
2.1.2 BFS版本
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){
    queue<pair<int, int>> myque;
    myque.push({x, y});
    visited[x][y]=true;
    while(!myque.empty()){
        pair<int, int> node = myque.front(); myque.pop();
        for(int i=0; i<4; i++){
            int next_x = node.first + dir[i][0];
            int next_y = node.second + dir[i][1];
            if (next_x < 0 || next_x >= grid.size() || next_y < 0 || next_y >= grid[0].size()) continue;
            if (visited[next_x][next_y]==false && grid[next_x][next_y]==1){
                myque.push({next_x, next_y});
                visited[next_x][next_y] = true;
            }
            
        }
    }
}

int main(){
    // 1 处理输入
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    int x;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> x;
            if (x) grid[i][j] = 1;
        }
    }
    // 2 处理岛屿数量
    int result = 0;
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if (visited[i][j] == false && grid[i][j] == 1){
                result++;
                bfs(grid, visited, i, j);
            }
        }
    }
    // 3 打印结果
    cout << result;
    return 0;
}

2.2 岛屿的最大面积

题目描述
给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。
输入描述
第一行包含两个整数 N, M，表示矩阵的行数和列数。后续 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。
输出描述
输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。
输入示例
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
输出示例
4

解题思路：

  • 1 使用图遍历算法，在每个岛屿内部遍历时记录走过的陆地的数量，保留最大值给全局变量。
  • 2 以下算法为了方便只使用DFS。
2.2.1 DFS

我们可以看到思路很简单，使用了一个count全局变量用来记录递归中遍历过的陆地。

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int count = 0;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){
    if (visited[x][y] == true || grid[x][y] == 0) return ;
    visited[x][y] = true;
    count++;
    for(int i=0; i < 4; i++){
        int next_x = x + dir[i][0];
        int next_y = y + dir[i][1];
        if (next_x < 0 || next_y < 0 || next_x >= grid.size() || next_y >= grid[0].size()) continue;
        dfs(grid, visited, next_x, next_y);
    }
}

int main(){
    // 1 处理输入
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    int x;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> x;
            if (x) grid[i][j] = 1;
        }
    }
    // 2 处理岛屿数量
    int result = 0;
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if (visited[i][j] == false && grid[i][j] == 1){
                count = 0;
                dfs(grid, visited, i, j);
                result = max(result, count);
            }
        }
    }
    // 3 打印结果
    cout << result;
    return 0;
}

2.3 孤岛的总面积

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。

输入描述
第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0。
输出描述
输出一个整数，表示所有孤岛的总面积，如果不存在孤岛，则输出 0。
输入示例
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
输出示例
1

解题思路：

  • 1 想清楚什么是孤岛，如何判断孤岛，再去进行图遍历
  • 2 孤岛的定义：没有触碰到边缘。

需要注意的地方：

  • 1 不能运行到一半发现边缘就立即返回，这样会导致下一次还未来得及将visited[i][j]置为True的地方被当做是孤岛面积。
  • 2 故需要全部遍历完成后，如果遇到边缘，则整个遍历面积为0.
2.3.1 DFS
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int count = 0;
int flag = 0;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){
    if (visited[x][y] == true || grid[x][y] == 0) return ;
    visited[x][y] = true;
    count++;
    for(int i=0; i < 4; i++){
        int next_x = x + dir[i][0];
        int next_y = y + dir[i][1];
        if (next_x < 0 || next_y < 0 || next_x >= grid.size() || next_y >= grid[0].size()){
            flag = 1;
            continue;
        }
        dfs(grid, visited, next_x, next_y);
    }
}

int main(){
    // 1 处理输入
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    int x;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> x;
            if (x) grid[i][j] = 1;
        }
    }
    // 2 处理岛屿数量
    int result = 0;
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if (visited[i][j] == false && grid[i][j] == 1){
                count = 0;
                flag = 0;
                dfs(grid, visited, i, j);
                if (flag == 0)
                    result += count;
            }
        }
    }
    // 3 打印结果
    cout << result;
    return 0;
}

2.4 沉没孤岛

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要将所有孤岛“沉没”，即将孤岛中的所有陆地单元格（1）转变为水域单元格（0）。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。

之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述
输出将孤岛“沉没”之后的岛屿矩阵。 注意：每个元素后面都有一个空格
输入示例
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
输出示例
1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 1 1

解题思路：

  • 1 从岛屿的四周开始遍历，将遍历过的陆地的visited[i][j]=True。
  • 2 最后直接将visited[i][j]为False的陆地的grid值直接改为0.

2.5 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

解题思路：

  • 1 与上述的遍历不同，这道题的遍历需要将匹配的数组跟随进行传参和判断。
  • 2 与上述遍历不同，该题的已访问路径只能通过回溯设定。

具体代码：

class Solution {
public:
    bool dfs(vector<vector<char>>& board, int i, int j, string word, int k){
        // 1 匹配成功
        if (k == word.size()) return true;
        // 2 越界或者匹配失败
        if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() || board[i][j] != word[k]) return false;
        // 3 访问过的路径设置不可访问
        int temp = board[i][j];
        board[i][j] = 0;
        // 4 递归
        bool ans = dfs(board, i+1, j, word, k+1) || dfs(board, i-1, j, word, k+1) ||
                   dfs(board, i, j-1, word, k+1) || dfs(board, i, j+1, word, k+1);
        // 5 回溯
        board[i][j] = temp;
        return ans;
    }

    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if (dfs(board, i, j, word, 0)) return true;
            }
        }
        return false;
    }
};

By crabboss

Related Post

经典算法模版

回溯篇 – N皇后

crabboss
经典算法模版

动态规划 – 背包问题 – 新

crabboss
经典算法模版

二分法进阶

crabboss

You Missed

Paper Share

Black-Box Prompt Optimization: Aligning Large Language Modelswithout Model Training

Paper Share

LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding

大模型

RAG和Long-Context的看法

大模型

大模型如何缓解微调过程的遗忘问题？