DFS/BFS 图论基础与海岛问题实战 (C/C++)
系统讲解了图论中的 DFS 与 BFS 遍历算法,提供了 C++ 代码模板及邻接表、邻接矩阵的实现示例。内容涵盖所有可达路径、岛屿数量、岛屿面积、孤岛总面积、沉没孤岛、水流问题、建造最大岛屿、岛屿周长、字符串接龙及有向图连通性等经典练习题,旨在帮助读者通过实战掌握图论基础与算法应用。

系统讲解了图论中的 DFS 与 BFS 遍历算法,提供了 C++ 代码模板及邻接表、邻接矩阵的实现示例。内容涵盖所有可达路径、岛屿数量、岛屿面积、孤岛总面积、沉没孤岛、水流问题、建造最大岛屿、岛屿周长、字符串接龙及有向图连通性等经典练习题,旨在帮助读者通过实战掌握图论基础与算法应用。

图论的遍历主要由 DFS(深度优先搜索)与 BFS(广度优先搜索)决定。
掌握知识点不能仅靠概念,需通过实践巩固。以下使用 DFS 遍历邻接表与邻接矩阵进行练手。
void dfs(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择:本节点相连的其他节点) {
处理节点;
dfs(图,选择的节点);
// 回溯,撤销处理的结果
}
}
题目描述 给定一个有 n 个节点的有向无环图,节点编号从 1 到 n。请编写函数,找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。
输入描述 第一行包含两个整数 N,M,表示图中拥有 N 个节点,M 条边。 后续 M 行,每行包含两个整数 s 和 t,表示图中的 s 节点与 t 节点中有一条路径。
输出描述
输出所有的可达路径,路径中所有节点之间空格隔开,每条路径独占一行。如果不存在任何一条路径,则输出 -1。
注意输出的序列中,最后一个节点后面没有空格!例如正确的答案是 1 3 5,而不是 1 3 5 。
数据范围 图中不存在自环、平行边。1 <= N <= 100, 1 <= M <= 500。
#include <iostream>
#include <vector>
using namespace std;
const int N = 105;
int arr[N][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 = 1; i <= n; ++i) {
if (arr[k][i] == 1) {
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;
arr[x][y] = 1;
}
cur.emplace_back(1);
dfs(1, n);
if (res.size() == 0) {
cout << -1 << endl;
} else {
for (auto vec : res) {
for (int i = 0; i < vec.size() - 1; ++i) {
cout << vec[i] << " ";
}
cout << vec[vec.size() - 1] << endl;
}
}
return 0;
}
#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.size() == 0) {
cout << -1 << endl;
} else {
for (auto vec : res) {
for (int i = 0; i < vec.size() - 1; ++i) {
cout << vec[i] << " ";
}
cout << vec[vec.size() - 1] << 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 >= grid.size() || x < 0 || y >= grid[0].size() || y < 0)
continue;
if (!used[x][y]) {
q.push({x, y});
}
}
}
}
通过'岛屿问题'磨炼遍历的基本式。以下是经典板子题。
题目描述 给定一个由 1(陆地)和 0(水)组成的矩阵,计算岛屿的数量。岛屿由水平或垂直方向上相邻的陆地连接而成。
输入描述 第一行包含两个整数 N, M。后续 N 行,每行包含 M 个数字。
输出描述 输出一个整数,表示岛屿的数量。
数据范围 1 <= N, M <= 50
#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 x_cur = x + dir[i][0];
int y_cur = y + dir[i][1];
if (!used[x_cur][y_cur] && arr[x_cur][y_cur] == 1) {
used[x_cur][y_cur] = true;
dfs(x_cur, y_cur);
}
}
}
int main() {
int n, m;
int cnt = 0;
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);
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;
}
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int result = 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())
continue;
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, 0));
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];
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;
}
题目描述 计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。
数据范围 1 <= M, N <= 50
#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};
int cur_area;
int max_area;
void dfs(int x, int y) {
for (int i = 0; i < 4; ++i) {
int x_cur = x + dir[i][0];
int y_cur = y + dir[i][1];
if (!used[x_cur][y_cur] && arr[x_cur][y_cur] == 1) {
used[x_cur][y_cur] = true;
cur_area++;
dfs(x_cur, y_cur);
}
}
}
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);
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;
}
题目描述 计算所有孤岛的总面积。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。
#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 cur_x = x + dir[i][0];
int cur_y = y + dir[i][1];
if (cur_x < 0 || cur_x >= m || cur_y < 0 || cur_y >= n)
continue;
if (used[cur_x][cur_y] || arr[cur_x][cur_y] == 0)
continue;
used[cur_x][cur_y] = true;
dfs(cur_x, cur_y);
}
}
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] == 0) continue;
used[i][0] = true;
dfs(i, 0);
}
for (int i = 0; i < m; ++i) {
if (used[i][n - 1] || arr[i][n - 1] == 0) continue;
used[i][n - 1] = true;
dfs(i, n - 1);
}
for (int i = 0; i < n; ++i) {
if (used[0][i] || arr[0][i] == 0) continue;
used[0][i] = true;
dfs(0, i);
}
for (int i = 0; i < n; ++i) {
if (used[m - 1][i] || arr[m - 1][i] == 0) continue;
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;
}
题目描述 将所有孤岛'沉没',即将孤岛中的所有陆地单元格(1)转变为水域单元格(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 nextX = x + dir[i][0];
int nextY = y + dir[i][1];
if (nextX < 0 || nextX >= grid.size() || nextY < 0 || nextY >= grid[0].size())
continue;
if (grid[nextX][nextY] == 1 && !used[nextX][nextY]) {
used[nextX][nextY] = true;
dfs(grid, used, nextX, nextY);
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
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);
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] && used[i][j])
cout << 1 << " ";
else
cout << 0 << " ";
}
cout << endl;
}
return 0;
}
题目描述 确定那些单元格,从这些单元格出发的水可以达到第一组边界和第二组边界。
注意 本题需要建立记忆化搜索,否则会造成无限递归。
#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 cur_x = x + dir[i][0];
int cur_y = y + dir[i][1];
if (cur_x < 0 || cur_x >= n || cur_y < 0 || cur_y >= m)
continue;
if (cur_arr[cur_x][cur_y] != 0)
continue;
if (arr[x][y] <= arr[cur_x][cur_y]) {
cur_arr[cur_x][cur_y] = flag;
dfs(cur_arr, flag, cur_x, cur_y);
}
}
}
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;
}
题目描述 最多可以将矩阵中的一格水变为一块陆地,求执行此操作之后,矩阵中最大的岛屿面积是多少。
#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)
continue;
int cnt = 0;
dfs(i, j, mark, cnt);
umap[mark++] = cnt;
}
}
unordered_set<int> uset;
int max_all = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (arr[i][j] != 0)
continue;
uset.clear();
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)
cout << umap[arr[0][0]] << endl;
else
cout << max_all << endl;
return 0;
}
题目描述 计算岛屿的周长。只有'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) {
int cur_x = x + dir[i][0];
int cur_y = y + dir[i][1];
dfs(cur_x, cur_y);
}
}
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;
}
题目描述 找到从 beginStr 到 endStr 的最短转换序列中的字符串数目。每次转换只能改变一个位置的字符。
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;
unordered_map<string, int> umap;
unordered_set<string> uset;
bool get_cnt(string str1, string str2) {
if (str1.size() != str2.size())
return false;
int cnt = 0;
for (int i = 0; i < str1.size(); ++i) {
if (str1[i] != str2[i])
cnt++;
}
if (cnt != 1)
return false;
return true;
}
int main() {
int n;
string begin_str, end_str;
cin >> n >> begin_str >> end_str;
for (int i = 0; i < n; ++i) {
string str;
cin >> str;
uset.insert(str);
}
queue<pair<string, int>> q;
q.emplace(begin_str, 1);
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.emplace(str_cur, cnt + 1);
q.emplace(str_cur, cnt + 1);
}
}
cout << 0 << endl;
return 0;
}
题目描述 给定一个有向图,从 1 号节点开始,如果可以从 1 号节点的边可以到达任何节点,则输出 1,否则输出 -1。
#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;
}

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML 转 Markdown 互为补充。 在线工具,Markdown 转 HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML 转 Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online