使用C++用邻接表实现图的广度优先遍历和深度优先遍历,简单点
时间: 2023-10-04 17:07:30 浏览: 121
C++无向图深度优先和广度优先遍历(编译可运行).rar
5星 · 资源好评率100%
好的,这里给出一个简单的邻接表实现图的广度优先遍历和深度优先遍历的示例代码:
```cpp
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
const int MAXN = 1005;
vector<int> G[MAXN]; // 邻接表存储图
bool vis[MAXN]; // 记录节点是否被访问过
void bfs(int s) {
queue<int> q;
q.push(s);
vis[s] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " ";
for (int i = 0; i < G[u].size(); ++i) {
int v = G[u][i];
if (!vis[v]) {
q.push(v);
vis[v] = true;
}
}
}
}
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);
}
}
}
void init() {
for (int i = 0; i < MAXN; ++i) {
G[i].clear();
vis[i] = false;
}
}
int main() {
int n, m;
cin >> n >> m;
init();
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
cout << "BFS: ";
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
bfs(i);
}
}
cout << endl;
memset(vis, false, sizeof(vis));
cout << "DFS: ";
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
dfs(i);
}
}
cout << endl;
return 0;
}
```
在上面的代码中,我们使用 `vector` 来存储邻接表,使用 `bool` 类型数组 `vis` 来记录节点是否已经被访问过。广度优先遍历使用了一个队列来实现,而深度优先遍历使用了递归的方式实现。
这里的 `init()` 函数用于初始化邻接表和访问标记等。在主函数中,我们通过输入图的节点数 `n` 和边数 `m`,并对每条边建立邻接表,然后使用广度优先遍历和深度优先遍历依次遍历整个图。
阅读全文