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 neighbor : graph[k]) {
        cur.emplace_back(neighbor);
        dfs(neighbor, 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].push_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）。

通用 BFS 框架：

// 方向偏移量：下、上、右、左
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 [x, y] = q.front();
        q.pop();
        
        for (int i = 0; i < 4; ++i) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            
            // 边界检查
            if (nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size()) {
                if (!used[nx][ny] && grid[nx][ny] == 1) {
                    used[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
    }
}

经典岛屿问题系列

通过一系列变体题目，可以彻底掌握 DFS/BFS 在网格中的应用。

1. 岛屿数量

计算矩阵中由 1 组成的连通区域数量。核心思想是：每发现一个未访问的陆地，计数器加一，并启动一次 DFS/BFS 将该岛屿所有相连陆地标记为已访问。

2. 岛屿的最大面积

在遍历过程中累加当前岛屿的节点数，并与全局最大值比较。注意每次新岛屿开始时重置局部计数器。

3. 孤岛的总面积

孤岛指不接触矩阵边缘的岛屿。策略是先遍历四条边上的陆地，将所有能到达边缘的岛屿标记（如设为 2），剩余未被标记的 1 即为孤岛。

4. 沉没孤岛

将上述孤岛全部变为水域（0）。逻辑同上一题，只是最后输出时将标记过的部分还原或修改。

5. 水流问题

判断哪些单元格的水既能流向左上边界，也能流向右下边界。采用逆向思维：从两个边界分别进行 Flood Fill（洪水填充），记录能到达的区域，取交集即可。

6. 建造最大岛屿

最多将一格 0 变为 1。先给每个现有岛屿染色并记录面积，然后遍历每个 0，查看其四周不同颜色的岛屿，累加面积 +1 更新最大值。

7. 岛屿的周长

统计陆地与水域或边界的交界线。遍历时若越界或遇到水域，周长加一。

8. 字符串接龙

本质是最短路径问题。将字典中的单词视为节点，相差一个字母的单词连边。使用 BFS 配合去重集合（Set/Map）可高效找到最短转换序列。

9. 有向图的完全联通

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

掌握这些基础模型后，面对复杂的图论问题，往往能拆解为类似的遍历任务。关键是灵活选择 DFS 或 BFS，并注意边界条件与状态标记。