创建无向图的邻接矩阵的深度广度c++
时间: 2024-01-03 13:05:03 浏览: 26
邻接矩阵是一种表示图的数据结构,其中矩阵中的元素表示图中每个节点之间的边。对于无向图来说,邻接矩阵是对称的。
以下是使用邻接矩阵创建无向图并进行深度优先搜索(DFS)和广度优先搜索(BFS)的C++代码:
```c++
#include<iostream>
#include<queue>
using namespace std;
#define MAX 100
int graph[MAX][MAX], visited[MAX], n;
queue<int> q;
void create_graph(){
int i, max_edges, origin, destin;
cout<<"Enter number of nodes: ";
cin>>n;
max_edges = n*(n-1)/2; //maximum number of edges for n nodes
for(i=1; i<=max_edges; i++){
cout<<"Enter edge "<<i<<" (-1 -1 to quit): ";
cin>>origin>>destin;
if((origin == -1) && (destin == -1)){
break;
}
if(origin<0 || origin>=n || destin<0 || destin>=n){
cout<<"Invalid edge!\n";
i--;
}
else{
graph[origin][destin] = 1;
graph[destin][origin] = 1;
}
}
}
void DFS(int node){
int i;
visited[node] = 1;
cout<<node<<" ";
for(i=0; i<n; i++){
if(graph[node][i] == 1 && visited[i] == 0){
DFS(i);
}
}
}
void BFS(int node){
int i, next_node;
visited[node] = 1;
cout<<node<<" ";
q.push(node);
while(!q.empty()){
next_node = q.front();
q.pop();
for(i=0; i<n; i++){
if(graph[next_node][i] == 1 && visited[i] == 0){
visited[i] = 1;
cout<<i<<" ";
q.push(i);
}
}
}
}
int main(){
int i, start_node;
create_graph();
cout<<"Enter starting node for DFS and BFS: ";
cin>>start_node;
cout<<"DFS Traversal: ";
DFS(start_node);
cout<<"\n";
for(i=0; i<n; i++){
visited[i] = 0;
}
cout<<"BFS Traversal: ";
BFS(start_node);
cout<<"\n";
return 0;
}
```
在这个程序中,用户需要输入节点数和每个节点之间的边,直到输入-1 -1为止。然后,使用邻接矩阵表示无向图。接下来,用户需要输入搜索的起始节点,然后进行深度优先搜索和广度优先搜索。在DFS和BFS函数中,我们使用visited数组来跟踪已访问过的节点,并使用递归和队列来遍历整个图。