2023年7月9日发(作者：)

图的遍历——深度优先搜索和⼴度（宽度）优先搜索（含例题）专栏导读及⽬录深度优先搜索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++库⾥封装的队列的，这⾥额外写⼀个不使⽤封装队列的⽅法，就是⾃⼰使⽤⼀个数组来模拟操作，见下⽅代码：#includeusing 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<>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辆车，按照编号先后发车，夹在其它车流中，缓缓前⾏。 路边有个死胡同，只能容⼀辆车通过，是临时的检查站，如图【】所⽰。

X星球太死板，要求每辆路过的车必须进⼊检查站，也可能不检查就放⾏，也可能仔细检查。 如果车辆进⼊检查站和离开的次序可以任意交错。那么，该车队再次上路后，可能的次序有多少种？ 为了⽅便起见，假设检查站可容纳任意数量的汽车。 显然，如果车队只有1辆车，可能次序1种；2辆车可能次序2种；3辆车可能次序5种。 现在⾜⾜有16辆车啊，亲！需要你计算出可能次序的数⽬ 这是⼀个整数，请通过浏览器提交答案，不要填写任何多余的内容（⽐如说明性⽂字）。

#includeusing 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<#includeconst 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

} return 0;}

⽅法⼆：⽤BFS解决#includeusing 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 q; p.x=x; p.y=y; (p); while(!()){ p=(); (); 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; (t); } } }}int main(){ while(scanf("%d %d",&n,&m)&&(n+m)){ memset(vis,0,sizeof vis); cnt=0; for(int i=0;i