DFS 与 BFS 实战：从图论遍历到岛屿问题详解

利用邻接表进行深搜

#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）作为媒介。虽然理论上栈也能用，但队列更符合层级遍历的逻辑。

// 定义四个方向的偏移量
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});
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        used[cur.first][cur.second] = true;
        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() && !used[x][y]) {
                q.push({x, y});
            }
        }
    }
}

经典岛屿问题系列

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

1. 岛屿数量

给定由 1（陆地）和 0（水）组成的矩阵，计算岛屿数量。相邻的陆地算作同一岛屿。

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) {
    for (int i = 0; i < 4; ++i) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if (nx >= 0 && nx < 55 && ny >= 0 && ny < 55 && !used[nx][ny] && arr[nx][ny] == 1) {
            used[nx][ny] = true;
            dfs(nx, ny);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> arr[i][j];
    memset(used, false, sizeof used);
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (!used[i][j] && arr[i][j] == 1) {
                used[i][j] = true;
                cnt++;
                dfs(i, j);
            }
    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() &&
                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. 岛屿的最大面积

在岛屿数量的基础上，计算组成岛屿的陆地总数，并取最大值。

#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) {
    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 < N && !used[nx][ny] && arr[nx][ny] == 1) {
            used[nx][ny] = true;
            cur_area++;
            dfs(nx, ny);
        }
    }
}

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

3. 孤岛的总面积

孤岛是指完全被水域包围且不接触边缘的岛屿。思路是先标记所有接触边缘的岛屿，剩下的即为孤岛。

#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 < m && ny >= 0 && ny < n && !used[nx][ny] && arr[nx][ny] == 1) {
            used[nx][ny] = true;
            dfs(nx, ny);
        }
    }
}

int main() {
    cin >> m >> n;
    memset(used, false, sizeof used);
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            cin >> arr[i][j];
    // 标记边界上的岛屿
    for (int i = 0; i < m; ++i) {
        if (!used[i][0] && arr[i][0] == 1) { used[i][0] = true; dfs(i, 0); }
        if (!used[i][n - 1] && arr[i][n - 1] == 1) { used[i][n - 1] = true; dfs(i, n - 1); }
    }
    for (int i = 0; i < n; ++i) {
        if (!used[0][i] && arr[0][i] == 1) { used[0][i] = true; dfs(0, i); }
        if (!used[m - 1][i] && arr[m - 1][i] == 1) { used[m - 1][i] = true; dfs(m - 1, i); }
    }
    int cnt = 0;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (!used[i][j] && arr[i][j] == 1) cnt++;
    cout << cnt << endl;
    return 0;
}

4. 沉没孤岛

将孤岛中的所有陆地变为水域。逻辑同上，只是最后输出时，未被标记为边界连接的陆地视为孤岛，将其置为 0。

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

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

void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& used, int x, int y) {
    used[x][y] = true;
    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() &&
            grid[nx][ny] == 1 && !used[nx][ny]) {
            used[nx][ny] = true;
            dfs(grid, used, nx, ny);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> grid[i][j];
    vector<vector<bool>> used(n, vector<bool>(m, false));
    // 标记边界可达的陆地
    for (int i = 0; i < n; ++i) {
        if (grid[i][0] && !used[i][0]) dfs(grid, used, i, 0);
        if (grid[i][m - 1] && !used[i][m - 1]) dfs(grid, used, i, m - 1);
    }
    for (int i = 0; i < m; ++i) {
        if (grid[0][i] && !used[0][i]) dfs(grid, used, 0, i);
        if (grid[n - 1][i] && !used[n - 1][i]) dfs(grid, used, n - 1, i);
    }
    // 输出：边界可达的保留 1，其余（孤岛）变为 0
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << (grid[i][j] && used[i][j] ? 1 : 0) << " ";
        }
        cout << endl;
    }
    return 0;
}

5. 水流问题

确定哪些单元格的水能同时流向第一组边界（左、上）和第二组边界（右、下）。需要建立记忆化搜索，避免重复遍历。

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

const int N = 105;
int n, m;
int arr[N][N];
int arr_one[N][N]; // 可达左/上
int arr_two[N][N]; // 可达右/下
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

void dfs(int cur_arr[N][N], int flag, 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) continue;
        if (cur_arr[nx][ny] != 0) continue;
        // 水从高往低流，所以当前高度 >= 下一个高度
        if (arr[x][y] >= arr[nx][ny]) {
            cur_arr[nx][ny] = flag;
            dfs(cur_arr, flag, nx, ny);
        }
    }
}

int main() {
    cin >> n >> m;
    memset(arr_one, 0, sizeof arr_one);
    memset(arr_two, 0, sizeof arr_two);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> arr[i][j];
    // 从左/上边界开始搜索
    for (int i = 0; i < n; ++i) {
        arr_one[i][0] = 1;
        dfs(arr_one, 1, i, 0);
        arr_two[i][m - 1] = 2;
        dfs(arr_two, 2, i, m - 1);
    }
    for (int i = 0; i < m; ++i) {
        arr_one[0][i] = 1;
        dfs(arr_one, 1, 0, i);
        arr_two[n - 1][i] = 2;
        dfs(arr_two, 2, n - 1, i);
    }
    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. 建造最大岛屿

最多可以将一格水变为一块陆地，求最大岛屿面积。策略是对每块岛屿染色编号，记录面积，然后尝试填充每个 0，连接周围不同颜色的岛屿。

#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;

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

void dfs(int x, int y, int mark, int& cnt) {
    if (x < 0 || x >= n || y < 0 || y >= m) return;
    if (arr[x][y] != 1) return;
    cnt++;
    arr[x][y] = mark;
    for (int i = 0; i < 4; ++i)
        dfs(x + dir[i][0], y + dir[i][1], mark, cnt);
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> arr[i][j];
    int mark = 2;
    unordered_map<int, int> umap;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (arr[i][j] == 1) {
                int cnt = 0;
                dfs(i, j, mark++, cnt);
                umap[mark - 1] = cnt;
            }
    int max_all = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (arr[i][j] == 0) {
                unordered_set<int> uset;
                int all = 1;
                for (int k = 0; k < 4; ++k) {
                    int x = i + dir[k][0];
                    int y = j + dir[k][1];
                    if (x < 0 || x >= n || y < 0 || y >= m) continue;
                    if (uset.find(arr[x][y]) != uset.end()) continue;
                    all += umap[arr[x][y]];
                    uset.insert(arr[x][y]);
                }
                max_all = max(max_all, all);
            }
    if (max_all == 0) {
        // 如果没有 0，或者全是 0，需特殊处理，这里假设至少有一个 1
        // 若全为 0，则填一个得 1
        bool hasOne = false;
        for(int i=0;i<n;++i) for(int j=0;j<m;++j) if(arr[i][j]==1) hasOne=true;
        if(!hasOne) cout << 1 << endl;
        else cout << umap[2] << endl; // 简化处理，实际应检查是否有未合并的岛
    } else {
        cout << max_all << endl;
    }
    return 0;
}

7. 岛屿的周长

统计岛屿边长。只有"1"与"0"或边界的交界处计入周长。

#include <iostream>
using namespace std;

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

void dfs(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m) {
        cnt++; // 越界即边界
        return;
    }
    if (used[x][y]) return;
    if (arr[x][y] == 0) {
        cnt++; // 遇到水即边界
        return;
    }
    used[x][y] = true;
    for (int i = 0; i < 4; ++i)
        dfs(x + dir[i][0], y + dir[i][1]);
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> arr[i][j];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (arr[i][j] == 1) {
                dfs(i, j);
                cout << cnt << endl;
                return 0;
            }
    return 0;
}

8. 字符串接龙

找到从 beginStr 到 endStr 的最短转换序列。每次只能改变一个字符，中间串必须在字典中。适合用 BFS 找最短路径。

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;

bool get_cnt(string str1, string str2) {
    if (str1.size() != str2.size()) return false;
    int cnt = 0;
    for (size_t i = 0; i < str1.size(); ++i)
        if (str1[i] != str2[i]) cnt++;
    return cnt == 1;
}

int main() {
    int n;
    string begin_str, end_str;
    cin >> n >> begin_str >> end_str;
    unordered_set<string> uset;
    for (int i = 0; i < n; ++i) {
        string str;
        cin >> str;
        uset.insert(str);
    }
    queue<pair<string, int>> q;
    q.emplace(begin_str, 1);
    unordered_map<string, int> umap;
    while (!q.empty()) {
        auto node = q.front();
        q.pop();
        string str = node.first;
        int cnt = node.second;
        if (get_cnt(str, end_str)) {
            cout << cnt + 1 << endl;
            return 0;
        }
        for (auto& str_cur : uset) {
            if (umap.find(str_cur) != umap.end()) continue;
            if (!get_cnt(str, str_cur)) continue;
            umap[str_cur] = cnt + 1;
            q.emplace(str_cur, cnt + 1);
        }
    }
    cout << 0 << endl;
    return 0;
}

9. 有向图的完全联通

判断从节点 1 是否能到达所有其他节点。使用邻接表和 DFS 即可。

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

const int N = 105;
int used[N];
vector<list<int>> graph(N);
int n, m;

void dfs(int i) {
    if (used[i] != 0) return;
    used[i] = 1;
    for (int node : graph[i])
        dfs(node);
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int s, t;
        cin >> s >> t;
        graph[s].push_back(t);
    }
    dfs(1);
    for (int i = 1; i <= n; ++i)
        if (used[i] == 0) {
            cout << -1 << endl;
            return 0;
        }
    cout << 1 << endl;
    return 0;
}

掌握这些模板和变体，基本就能应对大部分图论遍历类问题了。关键在于理解回溯、状态标记以及边界处理。