图的遍历代码实现c++
时间: 2023-11-30 09:41:38 浏览: 34
以下是C++中图的深度优先遍历(DFS)和广度优先遍历(BFS)的代码实现:
深度优先遍历(DFS):
```c++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int MAXN = 100; // 最大顶点数
vector<int> G[MAXN]; // 图的邻接表表示
bool vis[MAXN]; // 标记数组,记录每个顶点是否被访问过
void dfs(int u) {
vis[u] = true; // 标记当前顶点已被访问
cout << u << " "; // 输出当前顶点
for (int i = 0; i < G[u].size(); i++) { // 遍历当前顶点的所有邻接点
int v = G[u][i];
if (!vis[v]) { // 如果邻接点未被访问,则递归访问它
dfs(v);
}
}
}
int main() {
int n, m; // n为顶点数,m为边数
cin >> n >> m;
for (int i = 0; i < m; i++) { // 读入边
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u); // 无向图需要加上这一行
}
fill(vis, vis + MAXN, false); // 初始化标记数组
for (int u = 0; u < n; u++) { // 遍历所有顶点
if (!vis[u]) { // 如果当前顶点未被访问,则从它开始进行DFS
dfs(u);
}
}
return 0;
}
```
广度优先遍历(BFS):
```c++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 100; // 最大顶点数
vector<int> G[MAXN]; // 图的邻接表表示
bool vis[MAXN]; // 标记数组,记录每个顶点是否被访问过
void bfs(int u) {
queue<int> q; // 定义队列
q.push(u); // 将起始顶点加入队列
vis[u] = true; // 标记起始顶点已被访问
while (!q.empty()) { // 当队列非空时循环
int v = q.front(); // 取出队首元素
q.pop();
cout << v << " "; // 输出当前顶点
for (int i = 0; i < G[v].size(); i++) { // 遍历当前顶点的所有邻接点
int w = G[v][i];
if (!vis[w]) { // 如果邻接点未被访问,则将其加入队列
q.push(w);
vis[w] = true; // 标记邻接点已被访问
}
}
}
}
int main() {
int n, m; // n为顶点数,m为边数
cin >> n >> m;
for (int i = 0; i < m; i++) { // 读入边
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u); // 无向图需要加上这一行
}
fill(vis, vis + MAXN, false); // 初始化标记数组
for (int u = 0; u < n; u++) { // 遍历所有顶点
if (!vis[u]) { // 如果当前顶点未被访问,则从它开始进行BFS
bfs(u);
}
}
return 0;
}
```