DFS

图描述的是一些个体之间的关系。与线性表之间和二叉树之间不同的是，这些个体之间即不是前驱后继的顺序关系，也不是祖先后代的层次关系，而是错综复杂的网状关系。在图中一个比较重要的算法就是，小编接下来将要介绍的DFS算法。
下面通过一个具体的例子来介绍DFS算法--用DFS算法求联通块。
问题描述如下：油田（Oil Deposits UVa 572）
输入一个m行n列的字符矩阵，统计字符的"@"组成多少个八联块。如果两个字符"@"所在的格子相邻（横，竖，对角线方向）就说他们属于一个连通块。例如下图有两个八连块。

• • @
• @ @ * @
• @ @
  @ @ @ @
  @ @ * @
  分析如下：
  和二叉树的遍历一样，图也有DFS和BFS遍历。由于DFS更容易编写，一般用DFS找联通块：从每个"@"格子出发，递归遍历它周围的"@"格子。每次访问一个格子是就给它写上一个"联通分量编号"（即下面代码中的idx数组），这样就可以在访问之前检查它是否已经有了编号，从而避免同一个格子访问多次。

  #include#includeconst int maxn=100+5;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

  这道题目的算法有个好听的名字：种子填充（floodfill）。有兴趣的读者，可以在网络上查找相关资源。