DFS-创新互联
图描述的是一些个体之间的关系。与线性表之间和二叉树之间不同的是,这些个体之间即不是前驱后继的顺序关系,也不是祖先后代的层次关系,而是错综复杂的网状关系。在图中一个比较重要的算法就是,小编接下来将要介绍的DFS算法。
下面通过一个具体的例子来介绍DFS算法——用DFS算法求联通块。
问题描述如下:油田(Oil Deposits UVa 572)
输入一个m行n列的字符矩阵,统计字符的“@”组成多少个八联块。如果两个字符“@”所在的格子相邻(横,竖,对角线方向)就说他们属于一个连通块。例如下图有两个八连块。
-
-
-
- @
-
-
- @ @ * @
- @ @
@ @ @ @
@ @ * @
分析如下:
和二叉树的遍历一样,图也有DFS和BFS遍历。由于DFS更容易编写,一般用DFS找联通块:从每个“@”格子出发,递归遍历它周围的“@”格子。每次访问一个格子是就给它写上一个“联通分量编号”(即下面代码中的idx数组),这样就可以在访问之前检查它是否已经有了编号,从而避免同一个格子访问多次。#include
#include const 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)。有兴趣的读者,可以在网络上查找相关资源。
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
分享标题:DFS-创新互联
分享地址:http://scyanting.com/article/ddpdhp.html