连通块（dfs）java实现

目录
前言
例题链接
什么是连通块
具体思路
代码
注意
__
前言
连通块问题属于图的深度优先遍历dfs，本文章通过求连通块的个数简单案例，来介绍dfs解决连通块问题。
例题链接
http://oj.hzjingma.com/p/29?view=classic
例题中给到的是char类型地图，' . ' 代表不通路，' W ' 代表可连通，具体情况根据题目给的进行修改。
什么是连通块
如图整个表格为一个55二维数组，用来表示整个地图，白色填充为二维数组下标，最外层浅绿色代表地图的边界（为什么创建边界下文有提到），较为深颜色的为存放数据的二维数组，即下标（1~4）（1~4）。而颜色最深的块就是连通块，图中给出的就有三个连通块（上下左右连通，不考虑斜对连通）。

具体思路
除了行数列数以及开辟二维数组地图，还需要一个与地图同样大小的二维数组visitied，用来表示当前节点是否已经被访问过了。具体思路同图的dfs类似，当遍历到一个结点为1表示该节点可以连通（根据题目给的可能不同）并且没被访问过就进行深度遍历。
具体看代码。
代码

1. import java.util.Scanner;
2. /**
3. • 注意本例题中
4. • char[][]map地图 值为' . ' 代表不通，' W '代表可以连通
5. • int[][] visitied访问标记，初始值0未访问，1已访问
6. • @author lenovo
7. *
8. */
10. public class Main {
11. static int n,m,ans;
12. static char[][] map;
13. static int[][] vistied;
14. static int[][] step= {{1,0},{0,1},{-1,0},{0,-1}};
15. /*
16. • 上下左右移动遍历搜索
17. • 1 ,0 表示 x + 1 ，y + 0 向右移动，其他同理
18. • 如果为八向连通 则加上, { 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } 代表斜向移动
19. */
20. public static void main(String[] args) {
21. Scanner sc=new Scanner(System.in);
22. n=sc.nextInt();
23. m=sc.nextInt();
24. map=new charn+2;
25. vistied=new intn+2;
26. //初始化地图，创建边界
27. for (int i = 0; i <= n+1; i++) {
28. mapi = '.';
29. mapi = '.';
30. }
31. for (int i = 0; i <= m+1; i++) {
32. map0 = '.';
33. mapn+1 = '.';
34. }
35. //录入数据图（1~n）*（1~m）
36. for (int i = 1; i <= n; i++) {
37. String s=sc.next();
38. int k=0;
39. for (int j = 1; j <= m; j++) {
40. mapi=s.charAt(k++);
41. }
42. }
43. //从1-n 1-m一次遍历整张数据图
44. for (int x = 1; x <=n; x++) {
45. for (int y =1; y <=m; y++) {
46. //如果当前节点为'W'可以连通 并且为被访问则说明存在一个连通块
47. if(vistiedx ==0 && mapx == 'W') {
48. ans++;//连接块数量+1
49. vistiedx = 1;//当前节点标记为已经访问，以免重复判断
50. dfs(x,y);//进行深度优先遍历，将与其连通的所有节点都标记为已经访问。
51. //遍历完后从(1,1)到下一个节点(1,2)继续遍历，一次类推，直到所有节点全遍历完。
52. }
53. }
54. }
55. System.out.println(ans);
56. }
57. private static void dfs(int x, int y) {
58. /**
59. • step.length - 1 = 3
60. • 0 1 2 3 四步代表上下左右均走一遍
61. */
62. for (int i = 0; i <=(step.length - 1); i++) {
63. int newx=x+stepi; //x移动
64. int newy=y+stepi;//y移动
65. //如果移动后的节点 为 'W'可连通，并且未访问，则以移动后的节点为起点继续移动
66. if(mapnewx =='W' && vistiednewx ==0) {
67. vistiednewx = 1;//标记为已访问
68. dfs( newx, newy);
69. }
70. }
71. }
73. }

注意

   在实际应用时，为了防止当结点位于边界时，例如结点下标为(0,0)，其左结点下标为(-1,0),这时-1会越界。因此开辟二维数组的大小总是比题目中给到的n*m多两行，即开辟（n+2）*(m+2)大小的二维数组。