深度优先搜索
DFS基本思想
基本步骤：
1.从图中某个顶点v0出发，首先访问v0;
2.访问结点v0的第一个邻接点，以这个邻接点vt作为一个新节点，访问vt所有邻接点。直到以vt出发的所有节点都被访问到，回溯到v0的下一个未被访问过的邻接点，以这个邻结点为新节点，重复上述步骤。直到图中所有与v0相通的所有节点都被访问到。
3.若此时图中仍有未被访问的结点，则另选图中的一个未被访问的顶点作为起始点。重复深度优先搜索过程，直到图中的所有节点均被访问过。
图的遍历——DFS/BFS
图的遍历——DFS/BFS
基本代码结构
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.若此时图中仍有未被访问的结点，则另选图中的一个未被访问的顶点作为起始点。重复广度优先搜索过程，直到图中的所有节点均被访问过。
图的遍历——DFS/BFS
图的遍历——DFS/BFS
基本代码结构
通常用队列(先进先出,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<=n;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<=n;i++)if(!vis[i])bfs(i);
return 0;
}
下面给出一些例题和代码 及时练习效果更佳
出栈次序
X星球特别讲究秩序，所有道路都是单行线。一个甲壳虫车队，共16辆车，按照编号先后发车，夹在其它车流中，缓缓前行。
路边有个死胡同，只能容一辆车通过，是临时的检查站，如图【p1.png】所示。
X星球太死板，要求每辆路过的车必须进入检查站，也可能不检查就放行，也可能仔细检查。
如果车辆进入检查站和离开的次序可以任意交错。那么，该车队再次上路后，可能的次序有多少种？
为了方便起见，假设检查站可容纳任意数量的汽车。
显然，如果车队只有1辆车，可能次序1种；2辆车可能次序2种；3辆车可能次序5种。
现在足足有16辆车啊，亲！需要你计算出可能次序的数目
这是一个整数，请通过浏览器提交答案，不要填写任何多余的内容（比如说明性文字）。
图的遍历——DFS/BFS
#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;
}
网友评论