试实现邻接矩阵存储图的深度优先遍历。
时间: 2023-03-20 08:02:32 浏览: 142
好的,对于您的问题,我可以给出以下代码实现邻接矩阵存储图的深度优先遍历:
```
#include<iostream>
using namespace std;
const int MAXN=100;//图的最大节点数
int G[MAXN][MAXN];//邻接矩阵
bool visited[MAXN];//标记节点是否被访问过
//深度优先遍历函数
void DFS(int u,int n){
visited[u]=true;//标记当前节点为已访问
cout<<u<<" ";//输出当前节点的编号
for(int v=0;v<n;v++){
if(G[u][v]==1&&!visited[v]){//如果当前节点与v节点有边相连且v节点未被访问过
DFS(v,n);//递归遍历v节点
}
}
}
int main(){
int n,m;//n表示节点数,m表示边数
cin>>n>>m;
for(int i=0;i<m;i++){
int u,v;//表示一条边的两个端点
cin>>u>>v;
G[u][v]=G[v][u]=1;//在邻接矩阵中标记这条边
}
for(int i=0;i<n;i++){
visited[i]=false;//初始化所有节点为未访问状态
}
for(int i=0;i<n;i++){
if(!visited[i]){//如果节点i未被访问过
DFS(i,n);//从节点i开始进行深度优先遍历
}
}
return 0;
}
```
在该代码中,我们首先输入图的节点数n和边数m,然后输入每一条边的两个端点,并在邻接矩阵中标记这条边。接着,我们初始化所有节点为未访问状态,然后从未被访问的节点开始进行深度优先遍历,遍历过程中使用visited数组标记节点是否被访问过,并输出访问的节点编号。
阅读全文