专栏导读及目录/createprogram/article/details/86741044
深度优先搜索
DFS基本思想
基本步骤：
1.从图中某个顶点v0出发，首先访问v0;
2.访问结点v0的第一个邻接点，以这个邻接点vt作为一个新节点，访问vt所有邻接点。直到以vt出发的所有节点都被访问到，回溯到v0的下一个未被访问过的邻接点，以这个邻结点为新节点，重复上述步骤。直到图中所有与v0相通的所有节点都被访问到。
3.若此时图中仍有未被访问的结点，则另选图中的一个未被访问的顶点作为起始点。重复深度优先搜索过程，直到图中的所有节点均被访问过。
基本代码结构
void DFS( Point P ){for(所有P的邻接点K){if(K未被访问){if(k == e)return true;标记K;dfs(k);}}}
广度优先搜索
BFS基本思想
基本步骤：
1.从图中某个顶点v0出发，首先访问v0;
2.依次访问v0的各个未被访问的邻接点；
3.依次从上述邻接点出发，访问它们的各个未被访问的邻接点。
4.若此时图中仍有未被访问的结点，则另选图中的一个未被访问的顶点作为起始点。重复广度优先搜索过程，直到图中的所有节点均被访问过。
基本代码结构
通常用队列(先进先出,FIFO)实现初始化队列Q.Q={起点s}; 标记s为己访问;while (Q非空) {取Q队首元素u; u出队;if (u == 目标状态) {…}所有与u相邻且未被访问的点进入队列;标记与u相邻的点为已访问;}
DFS/BFS是竞赛中最常见的基础算法。虽然题目多种多样，但无外乎就是套用上文的程序片段，最主要的还是结合习题多练习达到熟能生巧。
这里呢，我想多讲一点。上面的BFS是使用C++库里封装的队列的，这里额外写一个不使用封装队列的方法，就是自己使用一个数组来模拟操作，见下方代码：
#include<bits/stdc++.h>using namespace std;int a[105][105],vis[105],n,m;//a是邻接矩阵 vis是标记 点是否被访问过void bfs(int k){ //k是当前点的名字int q[105];int f,r,i,j;//r表示当前BFS路过的点是第r个点q[1]=k;vis[k]=1;f=1;r=1;while(f<=r){i=q[f];for(j=1;j<=m;j++){if(a[i][j]>0&&!vis[j]){ //邻接矩阵中a[i][j]>0 表示 i和j连通r++;q[r]=j;vis[j]=1;}}f++;}for(i=1;i<=r;i++) cout<<q[i]<<" ";//输出当前BFS层的点的序号}int main(){int h,v1,v2;cin>>m;//点的数量cin>>n;//边的数量memset(a,0,sizeof(a));memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++){cin>>v1>>v2>>h;//每条边的 起点 终点 边长a[v1][v2]=a[v2][v1]=h;//无向图正反对接}for(int i=1;i<=m;i++)if(!vis[i])bfs(i);return 0;}
下面给出一些例题和代码 及时练习效果更佳
出栈次序
X星球特别讲究秩序，所有道路都是单行线。一个甲壳虫车队，共16辆车，按照编号先后发车，夹在其它车流中，缓缓前行。
路边有个死胡同，只能容一辆车通过，是临时的检查站，如图【p1.png】所示。
X星球太死板，要求每辆路过的车必须进入检查站，也可能不检查就放行，也可能仔细检查。
如果车辆进入检查站和离开的次序可以任意交错。那么，该车队再次上路后，可能的次序有多少种？
为了方便起见，假设检查站可容纳任意数量的汽车。
显然，如果车队只有1辆车，可能次序1种；2辆车可能次序2种；3辆车可能次序5种。
现在足足有16辆车啊，亲！需要你计算出可能次序的数目
这是一个整数，请通过浏览器提交答案，不要填写任何多余的内容（比如说明性文字）。
#include<iostream>using namespace std;long long count=0;void dfs(int a,int b,int k){if(a==16&&b==16&&k==32){count++;return;}if(a<=16&&b<=16&&a>=b&&k<32){dfs(a+1,b,k+1);dfs(a,b+1,k+1);}return ;}int main(){dfs(1,0,1);cout<<count;return 0;}
油田
输入一个m行n列的字符矩阵，统计字符“@”组成多少个八连块。如果两个字符“@”所在的格子相邻（八个方向），就说明他们属于同一个八连块。如图，有两个八连块
* * * * @
* @ @ * @
* @ * * @
@ @ @ * @
@ @ * * @
方法一：用DFS解决
#include<cstdio>#include<cstring>const int maxn=105;char pic[maxn][maxn];int m,n,idx[maxn][maxn];void dfs(int r,int c,int id){if(r<0||r>=m||c<0||c>=n) return;if(idx[r][c]>0||pic[r][c]!='@') return;idx[r][c]=id;for(int dr=-1;dr<=1;dr++)for(int dc=-1;dc<=1;dc++)if(dr!=0||dc!=0)dfs(r+dr,c+dc,id);}int main(){while(scanf("%d%d",&m,&n)==2&&m&&n){for(int i=0;i<m;i++) scanf("%s",pic[i]);memset(idx,0,sizeof(idx));int cnt=0;for(int i=0;i<m;i++)for(int j=0;j<n;j++)if(idx[i][j]==0&&pic[i][j]=='@') dfs(i,j,++cnt);printf("%d\n",cnt);}return 0;}
方法二：用BFS解决
#include<bits/stdc++.h>using namespace std;const int maxn=105;int m,n;int vis[maxn][maxn];char s[maxn][maxn];int cnt=0;int dir[8][2]={{0,1},{1,-1},{-1,-1},{-1,0},{0,-1},{-1,1},{1,0},{1,1}};typedef struct Node{int x,y;}node;void bfs(int x,int y){node p,t;queue<node> q;p.x=x;p.y=y;q.push(p);while(!q.empty()){p=q.front();q.pop();for(int i=0;i<8;i++){t.x=p.x+dir[i][0];t.y=p.y+dir[i][1];if(t.x<0||t.x>=n||t.x<0||t.y>=m){continue;}if(!vis[t.x][t.y]&&s[t.x][t.y]=='@'){vis[t.x][t.y]=1;q.push(t);}}}}int main(){while(scanf("%d %d",&n,&m)&&(n+m)){memset(vis,0,sizeof vis);cnt=0;for(int i=0;i<n;i++){scanf("%s",s[i]);}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(!vis[i][j]&&s[i][j]=='@'){vis[i][j]=1;cnt++;bfs(i,j);}}}printf("%d\n",cnt);}return 0;}
如果觉得《图的遍历——深度优先搜索和广度（宽度）优先搜索（含例题）》对你有帮助，请点赞、收藏，并留下你的观点哦！
