devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

图的遍历——深度优先搜索和广度（宽度）优先搜索（含例题）_深度遍历和广度遍历例题

作者：你好赵伟 | 2024-05-20 06:56:30

赞

踩

深度遍历和广度遍历例题

专栏导读及目录https://blog.csdn.net/createprogram/article/details/86741044

深度优先搜索

DFS基本思想

基本步骤：

1.从图中某个顶点v0出发，首先访问v0;  

2.访问结点v0的第一个邻接点，以这个邻接点vt作为一个新节点，访问vt所有邻接点。直到以vt出发的所有节点都被访问到，回溯到v0的下一个未被访问过的邻接点，以这个邻结点为新节点，重复上述步骤。直到图中所有与v0相通的所有节点都被访问到。

3.若此时图中仍有未被访问的结点，则另选图中的一个未被访问的顶点作为起始点。重复深度优先搜索过程，直到图中的所有节点均被访问过。

 

基本代码结构

  1. void DFS( Point P ){
  2.         for(所有P的邻接点K){
  3.                 if(K未被访问){
  4. 	            if(k == e)	
  5.                       return true;
  6.                        标记K;
  7.                    dfs(k);
  8.                 }
  9.         }
  10. }

广度优先搜索

BFS基本思想

基本步骤：

1.从图中某个顶点v0出发，首先访问v0;

2.依次访问v0的各个未被访问的邻接点；

3.依次从上述邻接点出发，访问它们的各个未被访问的邻接点。

4.若此时图中仍有未被访问的结点，则另选图中的一个未被访问的顶点作为起始点。重复广度优先搜索过程，直到图中的所有节点均被访问过。

 

基本代码结构

  1. 通常用队列(先进先出,FIFO)实现
  2.  
  3. 	初始化队列Q.
  4. 	Q={起点s}; 
  5.        标记s为己访问;
  6. 	while (Q非空) {
  7. 		取Q队首元素u; u出队;
  8. 		if (u == 目标状态) {…}
  9. 		所有与u相邻且未被访问的点进入队列;
  10. 		标记与u相邻的点为已访问;
  11. 	}

DFS/BFS是竞赛中最常见的基础算法。虽然题目多种多样，但无外乎就是套用上文的程序片段，最主要的还是结合习题多练习达到熟能生巧。

这里呢，我想多讲一点。上面的BFS是使用C++库里封装的队列的，这里额外写一个不使用封装队列的方法，就是自己使用一个数组来模拟操作，见下方代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a[105][105],vis[105],n,m;
  4. //a是邻接矩阵 vis是标记 点是否被访问过
  5. void bfs(int k){ //k是当前点的名字
  6. 		int q[105];
  7. 		int f,r,i,j;//r表示当前BFS路过的点是第r个点
  8. 		q[1]=k;
  9. 		vis[k]=1;
  10. 		f=1;r=1;
  11. 		while(f<=r){
  12. 			i=q[f];
  13. 			for(j=1;j<=m;j++){
  14. 				if(a[i][j]>0&&!vis[j]){ //邻接矩阵中a[i][j]>0 表示 i和j连通
  15. 					r++;
  16. 					q[r]=j;
  17. 					vis[j]=1;
  18. 				}
  19. 		
  20. 			}
  21. 			f++;
  22. 		}
  23. 		for(i=1;i<=r;i++) cout<<q[i]<<" ";//输出当前BFS层的点的序号
  24. }
  25. int main(){
  26. 	int h,v1,v2;
  27. 	cin>>m;//点的数量
  28. 	cin>>n;//边的数量
  29. 	memset(a,0,sizeof(a));
  30. 	memset(vis,0,sizeof(vis));
  31. 	for(int i=1;i<=n;i++){
  32. 		cin>>v1>>v2>>h;//每条边的  起点 终点 边长
  33. 		a[v1][v2]=a[v2][v1]=h;//无向图正反对接
  34. 	}
  35. 	for(int i=1;i<=m;i++)if(!vis[i])bfs(i);
  36. 	return 0;
  37. }

下面给出一些例题和代码 及时练习效果更佳

 

 

 

出栈次序

 

X星球特别讲究秩序，所有道路都是单行线。一个甲壳虫车队，共16辆车，按照编号先后发车，夹在其它车流中，缓缓前行。

    路边有个死胡同，只能容一辆车通过，是临时的检查站，如图【p1.png】所示。 

    X星球太死板，要求每辆路过的车必须进入检查站，也可能不检查就放行，也可能仔细检查。

    如果车辆进入检查站和离开的次序可以任意交错。那么，该车队再次上路后，可能的次序有多少种？

    为了方便起见，假设检查站可容纳任意数量的汽车。

    显然，如果车队只有1辆车，可能次序1种；2辆车可能次序2种；3辆车可能次序5种。

    现在足足有16辆车啊，亲！需要你计算出可能次序的数目 

这是一个整数，请通过浏览器提交答案，不要填写任何多余的内容（比如说明性文字）。   

  1. #include<iostream>
  2. using namespace std;
  3. long long count=0;
  4. void dfs(int a,int b,int k){
  5. 	if(a==16&&b==16&&k==32){
  6. 		
  7. 		count++;
  8. 		return;
  9. 	}
  10. 	
  11. 	if(a<=16&&b<=16&&a>=b&&k<32){
  12. 	
  13. 		dfs(a+1,b,k+1);
  14. 		dfs(a,b+1,k+1);
  15. 	}
  16. 	return ;	
  17. }
  18. int main(){
  19. 	dfs(1,0,1);
  20. 	cout<<count;
  21. 	return 0;
  22. }

油田

输入一个m行n列的字符矩阵，统计字符“@”组成多少个八连块。如果两个字符“@”所在的格子相邻（八个方向），就说明他们属于同一个八连块。如图，有两个八连块

  *   *   *   * @

  * @ @   * @

  * @   *   * @

@ @ @   * @

@ @   *   * @

方法一：用DFS解决

  1. #include<cstdio>
  2. #include<cstring>
  3. const int maxn=105;
  4. char pic[maxn][maxn];
  5. int m,n,idx[maxn][maxn];
  6. void dfs(int r,int c,int id){
  7. 	if(r<0||r>=m||c<0||c>=n) return;
  8. 	if(idx[r][c]>0||pic[r][c]!='@') return;
  9. 	idx[r][c]=id;
  10. 	for(int dr=-1;dr<=1;dr++)
  11. 		for(int dc=-1;dc<=1;dc++)
  12. 			if(dr!=0||dc!=0)dfs(r+dr,c+dc,id);
  13. }
  14. int main(){
  15. 	while(scanf("%d%d",&m,&n)==2&&m&&n){
  16. 		for(int i=0;i<m;i++) scanf("%s",pic[i]);
  17. 		memset(idx,0,sizeof(idx));
  18. 		int cnt=0;
  19. 		for(int i=0;i<m;i++)
  20. 			for(int j=0;j<n;j++)
  21. 				if(idx[i][j]==0&&pic[i][j]=='@') dfs(i,j,++cnt);
  22. 		printf("%d\n",cnt);		
  23. 	}
  24. 	return 0;
  25. }

 

方法二：用BFS解决

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int maxn=105;
  4. int m,n;
  5. int vis[maxn][maxn];
  6. char s[maxn][maxn];
  7. int cnt=0;
  8. int dir[8][2]={{0,1},{1,-1},{-1,-1},{-1,0},{0,-1},{-1,1},{1,0},{1,1}};
  9. typedef struct Node{
  10.     int x,y;
  11. }node;
  12. void bfs(int x,int y){
  13.     node p,t;
  14.     queue<node> q;
  15.     p.x=x;
  16.     p.y=y;
  17.     q.push(p);
  18.     while(!q.empty()){
  19.         p=q.front();
  20.         q.pop();
  21.         for(int i=0;i<8;i++){
  22.             t.x=p.x+dir[i][0];
  23.             t.y=p.y+dir[i][1];
  24.             if(t.x<0||t.x>=n||t.x<0||t.y>=m){
  25.                 continue;
  26.             }
  27.             if(!vis[t.x][t.y]&&s[t.x][t.y]=='@'){
  28.                 vis[t.x][t.y]=1;
  29.                 q.push(t);
  30.             }
  31.         }
  32.     }
  33. }
  34. int main()
  35. {
  36.     while(scanf("%d %d",&n,&m)&&(n+m)){
  37.         memset(vis,0,sizeof vis);
  38.         cnt=0;
  39.         for(int i=0;i<n;i++){
  40.             scanf("%s",s[i]);
  41.         }
  42.         for(int i=0;i<n;i++){
  43.             for(int j=0;j<m;j++){
  44.                 if(!vis[i][j]&&s[i][j]=='@'){
  45.                     vis[i][j]=1;
  46.                     cnt++;
  47.                     bfs(i,j);
  48.                 }
  49.             }
  50.         }
  51.         printf("%d\n",cnt);
  52.     }
  53.     return 0;
  54. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/596616
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号