用c++编写一个程序,定义图的邻接表存储结构并创建无向图的邻接表,在此基础上对无向图进行深度优先遍历,最后在主函数中进行调用演示。
时间: 2024-05-01 12:22:16 浏览: 107
好的,下面是代码实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
// 定义图的邻接表存储结构
struct Graph {
int V; // 图的顶点数
vector<vector<int>> adj; // 存储每个顶点的邻居节点
vector<bool> visited; // 标记节点是否被访问过
// 构造函数
Graph(int v) {
V = v;
adj.resize(V);
visited.resize(V, false);
}
// 添加无向边
void addEdge(int v, int w) {
adj[v].push_back(w);
adj[w].push_back(v);
}
// 深度优先遍历
void DFS(int v) {
visited[v] = true;
cout << v << " ";
for (int i = 0; i < adj[v].size(); i++) {
int w = adj[v][i];
if (!visited[w]) {
DFS(w);
}
}
}
};
int main() {
// 创建一个无向图
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 4);
// 对无向图进行深度优先遍历
cout << "深度优先遍历:";
g.DFS(0);
return 0;
}
```
运行结果:
```
深度优先遍历:0 1 2 3 4
```
阅读全文