c++语言创建无向图、对其进行深度优先的遍历,打印遍历结果
时间: 2024-02-15 19:01:30 浏览: 27
好的,下面是用C++语言创建无向图并进行深度优先遍历的示例代码:
```c++
#include<iostream>
#include<list>
#include<stack>
using namespace std;
class Graph{
int V; // 顶点的个数
list<int> *adj; // 邻接表
public:
Graph(int V);
void addEdge(int v, int w); // 添加边
void DFS(int s); // 深度优先遍历
};
Graph::Graph(int V){
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w){
adj[v].push_back(w);
adj[w].push_back(v);
}
void Graph::DFS(int s){
bool *visited = new bool[V];
for(int i=0; i<V; i++)
visited[i] = false;
stack<int> stack;
visited[s] = true;
stack.push(s);
while(!stack.empty()){
s = stack.top();
cout << s << " ";
stack.pop();
for(auto i=adj[s].begin(); i!=adj[s].end(); ++i){
if(!visited[*i]){
visited[*i] = true;
stack.push(*i);
}
}
}
}
int main(){
Graph g(5); // 创建图
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
cout << "深度优先遍历结果:";
g.DFS(0); // 从0号节点开始遍历
return 0;
}
```
输出结果为:
```
深度优先遍历结果:0 2 4 1 3
```
其中,`Graph`类表示图,`addEdge`方法用于添加边,`DFS`方法用于深度优先遍历,`stack`用于实现遍历过程中的节点存储。在`main`函数中,我们创建了一个5个节点的图,并对其进行深度优先遍历,从0号节点开始遍历。
希望这个示例代码能够帮助您理解如何用C++语言创建无向图及深度优先遍历。