前言：
和树的遍历类似，图的遍历也是从图中某点出发，然后按照某种方法对图中所有顶点进行访问，且仅访问一次。但是图的遍历相对树而言要更为复杂。因为图中的任意顶点都可能与其他顶点相邻，所以在图的遍历中必须记录已被访问的顶点，避免重复访问。根据搜索路径的不同，我们可以将遍历图的方法分为两种：广度优先搜索(BFS)和深度优先搜索(DFS)。
以书上的油田问题为例，p162的油田问题为例，解析的DFS的用法（floodfill）。其模板为：
//参考csdn：https://blog.csdn.net/weixin_43272781/article/details/82959089
int check(参数)
{
if(满足条件)
return 1;
return 0;
}
void dfs(int step)
{
判断边界
{
相应操作
}
尝试每一种可能
{
满足check条件
标记
继续下一步dfs(step+1)
恢复初始状态（回溯的时候要用到）
}
}
解决代码
#include<iostream>
#include<cstring>
using namespace std;
char pic[105][105];
int m,n,idx[105][105];
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(cin>>m>>n)
{
if(m==0||n==0) return 0;//若m为0或者n为0，则结束。
else
{
for(int i=0;i<m;i++) cin>>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);
cout<<cnt<<endl;
}
}
return 0;
}
测试数据如下：
Sample Input
1 1
3 5
@@*
@
@@*
1 8
@@*@
5 5
@ @@@ @@
@@@@ @@@
0 0
Sample Output
0
1
2
2
BFS暂时还不熟。
