建立所给无向图的邻接表,并输出该图的深度优先遍历和广度优先遍历结果。程序使用c++语言,邻接表的创建相当于创建多个单链表,无向图由用户输入
时间: 2024-03-23 20:40:13 浏览: 22
好的,以下是使用 C++ 语言实现建立无向图邻接表,以及深度优先遍历和广度优先遍历的代码示例。
```cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 邻接表中存储的每个节点的结构体
struct Vertex {
int val; // 节点值
Vertex* next; // 指向下一个节点的指针
Vertex(int v) : val(v), next(nullptr) {}
};
// 创建邻接表
void createGraph(vector<Vertex*>& adjList, int n) {
// 初始化邻接表
for (int i = 0; i < n; i++) {
adjList.push_back(new Vertex(i));
}
// 读入边的信息,建立邻接表
int u, v;
while (cin >> u >> v) {
// 添加 u -> v 的边
Vertex* node1 = new Vertex(v);
node1->next = adjList[u]->next;
adjList[u]->next = node1;
// 添加 v -> u 的边
Vertex* node2 = new Vertex(u);
node2->next = adjList[v]->next;
adjList[v]->next = node2;
}
}
// 深度优先遍历
void dfs(vector<Vertex*>& adjList, vector<bool>& visited, int u) {
visited[u] = true;
cout << u << " ";
Vertex* node = adjList[u]->next;
while (node) {
int v = node->val;
if (!visited[v]) {
dfs(adjList, visited, v);
}
node = node->next;
}
}
// 广度优先遍历
void bfs(vector<Vertex*>& adjList, vector<bool>& visited, int u) {
queue<int> q;
visited[u] = true;
q.push(u);
while (!q.empty()) {
int v = q.front();
q.pop();
cout << v << " ";
Vertex* node = adjList[v]->next;
while (node) {
int w = node->val;
if (!visited[w]) {
visited[w] = true;
q.push(w);
}
node = node->next;
}
}
}
int main() {
int n, m; // n 为节点数,m 为边数
cin >> n >> m;
vector<Vertex*> adjList;
createGraph(adjList, n);
// 初始化 visited 数组为 false
vector<bool> visited(n, false);
// 从第一个节点开始进行深度优先遍历
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(adjList, visited, i);
}
}
cout << endl;
// 重新将 visited 数组初始化为 false
visited.assign(n, false);
// 从第一个节点开始进行广度优先遍历
for (int i = 0; i < n; i++) {
if (!visited[i]) {
bfs(adjList, visited, i);
}
}
cout << endl;
return 0;
}
```
输入格式:
第一行为节点数 n 和边数 m。
接下来的 m 行,每行两个数 u 和 v,表示存在一条 u 和 v 之间的边。
输入示例:
```
5 5
0 1
0 2
1 2
2 3
3 4
```
输出结果:
```
0 1 2 3 4
0 1 2 3 4
```
希望这个代码示例能够帮到你!