图的遍历
1、DFS
- 目标：访问所有顶点，策略是沿着一条路走到底然后回溯
- DFS序列不唯一
| #include <bits/stdc++.h>
using namespace std;
const int V_NUM = 100; // 最大顶点数（邻接矩阵会占用 O(n^2) 空间，不能太大）
int G[V_NUM][V_NUM]; // 邻接矩阵，G[i][j] == 1 表示 i 和 j 之间有边
bool visited[V_NUM]; // visited[i] == true 表示节点 i 已访问
// 模拟访问某个节点的操作，这里简单输出
void visit(int v) {
cout << "访问节点: " << v << endl;
}
// 深度优先搜索，从节点 v 开始，n 是总顶点数
void DFS(int G[V_NUM][V_NUM], int v, int n) {
visit(v); // 访问当前节点
visited[v] = true; // 标记已访问
// 遍历所有可能的相邻节点
for (int i = 0; i < n; i++) {
// 如果节点 i 与当前节点 v 相连 且 尚未访问，则递归访问
if (G[v][i] == 1 && !visited[i]) {
DFS(G, i, n); // 递归访问邻接节点
}
}
}
int main() {
int n = 5; // 总顶点数，节点编号为 0~4
// 构建无向图：添加边（双向）
G[0][1] = G[1][0] = 1;
G[0][2] = G[2][0] = 1;
G[1][3] = G[3][1] = 1;
G[2][4] = G[4][2] = 1;
// 从节点 0 开始执行 DFS
DFS(G, 0, n);
return 0;
}
|
2、BFS
- 和二叉树的层序遍历（广度优先）一模一样，使用队列结构实现这个操作
| #include <bits/stdc++.h>
using namespace std;
const int V_NUM = 100;
int G[V_NUM][V_NUM]; // 邻接矩阵
bool visited[V_NUM]; // 标记是否访问过
void visit(int v) {
cout << "Visit: " << v << endl;
}
void BFS(int G[][V_NUM], int start) {
queue<int> Q;
Q.push(start);
visited[start] = true;
visit(start);
while (!Q.empty()) {
int v = Q.front();
Q.pop();
for (int i = 0; i < n; ++i) {
if (G[v][i] == 1 && !visited[i]) {
Q.push(i);
visited[i] = true;
visit(i);
}
}
}
}
int main() {
int n = 5; // 顶点个数，编号从 0 到 4
// 示例建图（无向图）
G[0][1] = G[1][0] = 1;
G[0][2] = G[2][0] = 1;
G[1][3] = G[3][1] = 1;
G[2][4] = G[4][2] = 1;
BFS(G, 0); // 从顶点 0 开始 BFS
return 0;
}
|
例题
e.g. 连通集
给定一个有 \(N\) 个顶点和 \(E\) 条边的无向图，请用深度优先遍历（DFS）和广度优先遍历（BFS）分别列出其所有的连通集。假设顶点从 \(0\) 到 \(N-1\) 编号。进行搜索时，假设总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入：输入第1行给出2个整数 \(N(0<N≤10)\) 和 \(E\) ，分别是图的顶点数和边数。随后 \(E\) 行，每行给出一条边的两个端点。每行中的数字之间用一个空格分隔。
输出：按照 \(\{v1v2…vk\}\) 的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。
样例
样例输入
| 8 6
0 7
0 1
2 0
4 1
2 4
3 5
|
样例输出
| {0 1 4 2 7}
{3 5}
{6}
{0 1 2 7 4}
{3 5}
{6}
|
| #include <bits/stdc++.h>
using namespace std;
const int V_NUM = 100; // 最大顶点数，实际可调小以避免内存爆炸
int G[V_NUM][V_NUM]; // 邻接矩阵定义
bool visited[V_NUM]; // 访问标记数组
void visit(int v) {
cout << v << " "; // 访问顶点V
}
// DFS
// G为邻接矩阵，v为当前访问的顶点
void DFS(int G[V_NUM][V_NUM], int v) {
visit(v);
visited[v] = true; // 标记顶点V被访问
// 判断是否存在边没有被访问
for (int i = 0; i < V_NUM; i++) {
if (G[v][i] == 1 && visited[i] == false) {
DFS(G, i); // 递归调用
}
}
}
// BFS
void BFS(int G[V_NUM][V_NUM], int start) {
queue<int> Q;
Q.push(start);
visited[start] = true; // 标记起始顶点已访问
visit(start); // 访问起始顶点
while (!Q.empty()) {
int v = Q.front(); // 获取队首元素
Q.pop(); // 弹出队首元素
for (int i = 0; i < V_NUM; i++) {
if (G[v][i] == 1 && !visited[i]) { // 如果存在边且未访问
Q.push(i); // 将顶点i加入队列
visited[i] = true; // 标记顶点i已访问
visit(i); // 访问顶点i
}
}
}
}
int main() {
int V_NUM, E_NUM;
cin >> V_NUM >> E_NUM;
// 初始化邻接矩阵
for (int i = 0; i < E_NUM; i++) {
int u, v;
cin >> u >> v; // 输入边的两个顶点
G[u][v] = G[v][u] = 1; // 无向图
}
for (int i = 0; i < V_NUM; i++) {
visited[i] = false; // 初始化访问标记数组为false
}
// 深度优先遍历
for (int i = 0; i < V_NUM; i++) {
if (visited[i])
continue; // 如果顶点i已经被访问过，跳过
else {
cout << "{";
DFS(G, i);
cout << "\b}"; // 删除最后一个空格
cout << endl;
}
}
// 重置访问标记数组
for (int i = 0; i < V_NUM; i++) {
visited[i] = false; // 初始化访问标记数组为false
}
// 广度优先遍历
for (int i = 0; i < V_NUM; i++) {
if (visited[i])
continue; // 如果顶点i已经被访问过，跳过
else {
cout << "{";
BFS(G, i);
cout << "\b}"; // 删除最后一个空格
cout << endl;
}
}
}
|