图的遍历 —— DFS、BFS
0.概要
本文主要从以下三个方面介绍图的遍历:
- 图的广度优先遍历(BFS)
- 图的深度优先遍历(DFS)
- 两种遍历一般性实现代码(C++)
1.图的广度优先遍历(BFS)
(1)树 (层次遍历) VS 图 (BFS——广度优先遍历)
(2)算法要点——BFS
- 连通图
- 非连通图
(3)遍历序列可变性
(4)空间复杂度
(5)时间复杂度
(6)广度优先生成树
- 对⾮连通图的⼴度优先遍历,可得到⼴度优先⽣成森林
1.图的深度优先遍历(DFS)
(1)算法要点
(2)遍历序列可变性
(3)空间复杂度
(4)时间复杂度
(5)图遍历练习
(6)图的遍历与图的连通性
- 无向图
- 有向图
3.实现代码(BFS + DFS)
#include<bits/stdc++.h>
using namespace std;
#define max 50
//两种遍历图的算法
int a[max][max]; //存储边
int n,k; //存储顶点和边
int flag[max]; //标记数组
queue<int> qu; //广搜队列
//深度优先遍历
void dfs(int i){
if(i>n){
return;
}
else{
for(int j=1;j<=n;j++){ //相邻顶点未必按照自然数访问
if(flag[j]==0&&a[i][j]==1){
flag[j]=1;
cout<<j<<" ";
dfs(j); //不需要回溯
}
}
}
}
//广度优先遍历
void bfs(int i){
qu.push(i);
flag[i]=1;
while(!qu.empty()){
int t=qu.front();
cout<<t<<" ";
qu.pop();
for(int j=1;j<=n;j++){ //相邻顶点全部进栈
if(flag[j]==0&&a[t][j]==1){
flag[j]=1;
qu.push(j);
}
}
}
}
//主函数
int main(){
cin>>n;
cin>>k;
memset(a,0,sizeof(a)); //初始化数组
int x=0;
int y=0;
//输入边之间信息,默认顶点值为1~N
for(int i=1;i<=k;i++){
cin>>x;
cin>>y;
a[x][y]=1;
a[y][x]=1;
}
cout<<"深搜:"<<endl;
dfs(1); //顶点1开始
cout<<endl;
memset(flag,0,sizeof(flag)); //重新初始化标记数组
cout<<"广搜:"<<endl;
bfs(1); //顶点2开始
return 0;
}
ertyuiiiohfss: 写的太好了
程序=探索+优化: 为什么大家愿意收藏却不愿意点赞呢
Alan_刘志强: 学习了,感谢大佬的分享
浅听微雨: 感觉你写的逻辑有点乱
2301_81108238: 博主,平行四边形第二个判定可以不是递增,常函数是不是也可以