DFS/BFS 专项练习：从海岛问题到图论基础应用 (C/C++)

利用邻接表进行深搜

邻接表适合稀疏图，空间复杂度为 O(N+M)。使用 vector<list<int>> 或 vector<vector<int>> 均可。

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

const int N = 105;
vector<list<int>> graph(N); // 邻接表
vector<int> cur;
vector<vector<int>> res;

void dfs(int k, int n) {
    if (k == n) {
        res.emplace_back(cur);
        return;
    }
    for (int i : graph[k]) {
        cur.emplace_back(i);
        dfs(i, n);
        cur.pop_back();
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        graph[x].emplace_back(y);
    }
    cur.emplace_back(1);
    dfs(1, n);

    if (res.empty()) {
        cout << -1 << endl;
    } else {
        for (const auto& vec : res) {
            for (size_t i = 0; i < vec.size() - 1; ++i) {
                cout << vec[i] << " ";
            }
            cout << vec.back() << endl;
        }
    }
    return 0;
}

BFS 基础实现

BFS 通常配合队列（Queue）使用，用于解决最短路径问题。核心在于按层遍历。

#include <queue>
#include <vector>
using namespace std;

// 方向数组：下、上、右、左
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

void bfs(vector<vector<int>>& grid, vector<vector<bool>>& used) {
    queue<pair<int, int>> q;
    q.push({0, 0});
    used[0][0] = true;

    while (!q.empty()) {
        auto cur = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i) {
            int x = cur.first + dir[i][0];
            int y = cur.second + dir[i][1];

            // 边界检查
            if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()) {
                if (!used[x][y] && grid[x][y] == 1) {
                    used[x][y] = true;
                    q.push({x, y});
                }
            }
        }
    }
}

经典岛屿问题系列

通过一系列岛屿相关的题目，可以系统训练 DFS/BFS 的边界处理与状态标记能力。

1. 岛屿数量

计算矩阵中由水平或垂直方向相邻陆地（1）组成的连通区域数量。

思路：遍历每个点，若发现未访问的陆地，则启动一次 DFS/BFS 将该岛屿所有部分标记为已访问，计数器加一。

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

const int N = 55;
int arr[N][N];
bool used[N][N];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

void dfs(int x, int y, int n, int m) {
    for (int i = 0; i < 4; ++i) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !used[nx][ny] && arr[nx][ny] == 1) {
            used[nx][ny] = true;
            dfs(nx, ny, n, m);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> arr[i][j];

    memset(used, false, sizeof used);
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (arr[i][j] == 1 && !used[i][j]) {
                used[i][j] = true;
                cnt++;
                dfs(i, j, n, m);
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

2. 岛屿的最大面积

在统计数量的基础上，计算单个岛屿包含的格子数最大值。

思路：DFS 过程中累加当前岛屿的面积，并维护全局最大值。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 55;
int arr[N][N];
bool used[N][N];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int cur_area, max_area;

void dfs(int x, int y, int n, int m) {
    for (int i = 0; i < 4; ++i) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !used[nx][ny] && arr[nx][ny] == 1) {
            used[nx][ny] = true;
            cur_area++;
            dfs(nx, ny, n, m);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> arr[i][j];

    memset(used, false, sizeof used);
    max_area = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (arr[i][j] == 1 && !used[i][j]) {
                cur_area = 1;
                used[i][j] = true;
                dfs(i, j, n, m);
                max_area = max(max_area, cur_area);
            }
        }
    }
    cout << max_area << endl;
    return 0;
}

3. 孤岛总面积

计算完全被水域包围（不接触矩阵边缘）的岛屿总面积。

思路：先对接触边缘的岛屿进行 DFS 标记（视为非孤岛），剩余未访问的陆地即为孤岛。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 55;
int arr[N][N];
bool used[N][N];
int n, m;
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

void dfs(int x, int y) {
    for (int i = 0; i < 4; ++i) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !used[nx][ny] && arr[nx][ny] == 1) {
            used[nx][ny] = true;
            dfs(nx, ny);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> arr[i][j];

    memset(used, false, sizeof used);
    // 标记边缘岛屿
    for (int i = 0; i < n; ++i) {
        if (arr[i][0] == 1 && !used[i][0]) { used[i][0] = true; dfs(i, 0); }
        if (arr[i][m - 1] == 1 && !used[i][m - 1]) { used[i][m - 1] = true; dfs(i, m - 1); }
    }
    for (int j = 0; j < m; ++j) {
        if (arr[0][j] == 1 && !used[0][j]) { used[0][j] = true; dfs(0, j); }
        if (arr[n - 1][j] == 1 && !used[n - 1][j]) { used[n - 1][j] = true; dfs(n - 1, j); }
    }

    int cnt = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (arr[i][j] == 1 && !used[i][j]) cnt++;

    cout << cnt << endl;
    return 0;
}

4. 沉没孤岛

将孤岛中的陆地变为水域。

思路：同孤岛总面积，标记边缘岛屿后，将未标记的陆地置为 0。

5. 水流问题

确定哪些单元格的水能同时流向第一组边界和第二组边界。

思路：反向思考。分别从两组边界出发进行 DFS/BFS，标记可达区域。取两个标记集合的交集。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 105;
int n, m;
int arr[N][N];
int arr_one[N][N], arr_two[N][N];
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

void dfs(int flag, int x, int y, int target_arr[][N]) {
    for (int i = 0; i < 4; ++i) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && target_arr[nx][ny] == 0) {
            if (arr[x][y] <= arr[nx][ny]) {
                target_arr[nx][ny] = flag;
                dfs(flag, nx, ny, target_arr);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> arr[i][j];

    memset(arr_one, 0, sizeof arr_one);
    memset(arr_two, 0, sizeof arr_two);

    // 从第一组边界（左、上）开始
    for (int i = 0; i < n; ++i) {
        arr_one[i][0] = 1;
        dfs(1, i, 0, arr_one);
    }
    for (int j = 0; j < m; ++j) {
        arr_one[0][j] = 1;
        dfs(1, 0, j, arr_one);
    }

    // 从第二组边界（右、下）开始
    for (int i = 0; i < n; ++i) {
        arr_two[i][m - 1] = 2;
        dfs(2, i, m - 1, arr_two);
    }
    for (int j = 0; j < m; ++j) {
        arr_two[n - 1][j] = 2;
        dfs(2, n - 1, j, arr_two);
    }

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (arr_one[i][j] == 1 && arr_two[i][j] == 2)
                cout << i << " " << j << endl;

    return 0;
}

6. 建造最大岛屿

最多将一格水变为一块陆地，求最大岛屿面积。

思路：先给现有岛屿染色编号并记录面积，然后遍历每个水域，尝试连接周围不同颜色的岛屿。

7. 岛屿的周长

计算岛屿的边界长度。

思路：遍历每个陆地格子，检查其上下左右四个方向，若越界或遇到水域，则周长加一。

8. 字符串接龙

找到从 beginStr 到 endStr 的最短转换序列。

思路：典型的 BFS 最短路径问题。每次转换一个字符，需确保中间词在字典中。使用队列存储当前字符串及步数，注意去重防止超时。

9. 有向图的完全联通

判断从节点 1 是否能到达所有其他节点。

思路：从节点 1 开始 DFS/BFS，统计访问到的节点数，若等于总节点数则输出 1，否则 -1。

掌握这些基础模型后，面对复杂的图论问题，往往能拆解为类似的遍历与状态更新逻辑。关键在于根据题意选择合适的存储结构与遍历策略。