DFS/BFS 专项练习：从海岛问题掌握图论基础（C++ 实现）

利用邻接表深搜

邻接表在稀疏图中更节省空间，遍历效率也更高。

#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 (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]) {
                    used[x][y] = true;
                    q.push({x, y});
                }
            }
        }
    }
}

岛屿问题系列实战

想要学好图论，必须熟练运用 DFS 与 BFS。下面通过经典的'岛屿问题'系列来磨炼遍历的基本式。

1. 岛屿数量

计算矩阵中由 1（陆地）和 0（水）组成的岛屿数量。

DFS 解法：遍历每个未访问的陆地，启动一次 DFS 标记整个岛屿。

#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;
}

BFS 解法：核心在于使用队列存储待访问坐标。

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

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

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

    while (!que.empty()) {
        pair<int, int> cur = que.front();
        que.pop();
        for (int i = 0; i < 4; ++i) {
            int nextY = cur.first + dir[i][0];
            int nextX = cur.second + dir[i][1];
            if (nextX >= 0 && nextX < grid[0].size() && nextY >= 0 && nextY < grid.size()) {
                if (grid[nextY][nextX] == 1 && !used[nextY][nextX]) {
                    used[nextY][nextX] = true;
                    que.push({nextY, nextX});
                }
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m));
    vector<vector<bool>> used(n, vector<bool>(m, false));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> grid[i][j];

    int result = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 1 && !used[i][j]) {
                result++;
                bfs(grid, used, i, j);
            }
        }
    }
    cout << result << endl;
    return 0;
}

2. 岛屿的最大面积

思路与岛屿数量类似，但在 DFS 过程中累加当前连通块的面积，并更新最大值。

3. 孤岛的总面积

孤岛指完全被水域包围且不接触边缘的岛屿。策略是先将与边缘相连的陆地全部标记为已访问（淹没），剩下的陆地即为孤岛。

4. 沉没孤岛

将上述逻辑反转，找到所有孤岛并将其标记为水域（0）。

5. 水流问题

这是一个逆推法的经典应用。分别从第一组边界（左、上）和第二组边界（右、下）出发进行 DFS/BFS，标记能到达的区域，最后取交集。

注意：本题务必建立记忆化搜索，否则会导致重复遍历甚至无限递归。

6. 建造最大岛屿

最多可以将一格水变为一块陆地。策略是对现有岛屿染色（打编号），记录每个岛屿的面积。遍历所有水域格子，尝试将其变为陆地，计算周围不同编号岛屿的面积之和。

7. 岛屿的周长

统计所有陆地格子四周与水域或边界的交界线数量。

8. 字符串接龙

典型的 BFS 最短路径问题。将字符串视为节点，相差一个字符的字符串连边。使用队列搜索从 beginStr 到 endStr 的最短序列。

9. 有向图的完全联通

从节点 1 开始遍历，检查是否所有节点都被访问过。若 used 数组中有未访问节点，则无法到达所有点。

图论的基础在于对遍历方式的灵活运用。多动手写代码，多画图分析，才能真正掌握这些算法的精髓。