生成c++代码(建立任意无向图,采用邻接矩阵存储,完成以下操作:对该图进行深度优先遍历,并输出遍历结果。对该图进行广度优先遍历,并输出遍历结果。)
时间: 2024-02-17 11:02:14 浏览: 91
建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历.doc
5星 · 资源好评率100%
以下是建立无向图并进行深度优先遍历和广度优先遍历的C++代码:
```c++
#include<iostream>
#include<queue>
using namespace std;
class Graph{
int vertices;
int** adj_matrix;
public:
Graph(int vertices);
void add_edge(int u, int v);
void dfs(int start);
void bfs(int start);
};
Graph::Graph(int vertices){
this->vertices = vertices;
adj_matrix = new int*[vertices];
for(int i=0;i<vertices;++i){
adj_matrix[i] = new int[vertices];
for(int j=0;j<vertices;++j){
adj_matrix[i][j] = 0;
}
}
}
void Graph::add_edge(int u, int v){
adj_matrix[u][v] = 1;
adj_matrix[v][u] = 1;
}
void Graph::dfs(int start){
bool* visited = new bool[vertices];
for(int i=0;i<vertices;++i){
visited[i] = false;
}
cout<<"DFS: ";
stack<int> s;
s.push(start);
while(!s.empty()){
int curr = s.top();
s.pop();
if(!visited[curr]){
visited[curr] = true;
cout<<curr<<" ";
for(int i=vertices-1;i>=0;--i){
if(adj_matrix[curr][i] == 1 && !visited[i]){
s.push(i);
}
}
}
}
}
void Graph::bfs(int start){
bool* visited = new bool[vertices];
for(int i=0;i<vertices;++i){
visited[i] = false;
}
cout<<"BFS: ";
queue<int> q;
q.push(start);
while(!q.empty()){
int curr = q.front();
q.pop();
if(!visited[curr]){
visited[curr] = true;
cout<<curr<<" ";
for(int i=0;i<vertices;++i){
if(adj_matrix[curr][i] == 1 && !visited[i]){
q.push(i);
}
}
}
}
}
int main(){
Graph g(5);
g.add_edge(0,1);
g.add_edge(0,2);
g.add_edge(1,3);
g.add_edge(2,4);
g.dfs(0);
cout<<endl;
g.bfs(0);
cout<<endl;
return 0;
}
```
解释一下代码:
1. 首先定义了一个图的类,需要传入顶点数初始化,同时使用邻接矩阵存储图。
2. `add_edge` 方法用于添加边,因为是无向图,所以需要同时在两个顶点之间添加边。
3. `dfs` 方法用于进行深度优先遍历,需要传入起点。
4. 在 `dfs` 方法中,使用栈来存储每一个顶点,先将起点加入栈中。然后从栈中取出一个顶点,如果该顶点没有被访问过,就将其标记为已访问,并输出它的编号。然后遍历与其相邻的未访问过的顶点,并将其加入栈中。
5. `bfs` 方法用于进行广度优先遍历,需要传入起点。
6. 在 `bfs` 方法中,使用队列来存储每一层遍历到的顶点,先将起点加入队列中。然后从队列中取出一个顶点,如果该顶点没有被访问过,就将其标记为已访问,并输出它的编号。然后遍历与其相邻的未访问过的顶点,并将其加入队列中。
最后运行程序,输出结果如下:
```
DFS: 0 2 4 1 3
BFS: 0 1 2 3 4
```
阅读全文