连通子图问题(DFS的递归和非递归实现)

问题定义（以下均为Java实现）

  输入一个 m m m行 n n n列的字符矩阵， 统计字符“@”组成多少个八连块。 如果两个字符“@”所在的格子相邻（ 横、 竖或者对角线方向） ， 就说它们属于同一个八连块。 例如， 下图有 3 3 3个八连块。

解题思路：深/广度优先遍历，记录已经遍历过的字符。深度优先遍历有不同的实现，下面是非递归（栈）或者递归的两种解法。

解法一

  基于栈的DFS，当遍历到某个字符时，入栈并标记该字符，然后继续判断该字符的相邻字符，当该字符没有相邻字符为“@”则出栈。代码如下：

1. 首先构造一个描述图节点的类Dot，包含实例属性r，c分别表示该字符所在行，所在列。其中关于get、set以及构造方法已经省略，此外为了判断是否已经遍历过，重写了equals和hashCode方法。

class Dot{
        private int r;
        private int c;
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Dot dot = (Dot) o;
            return getR() == dot.getR() &&
                    getC() == dot.getC();
        }

        @Override
        public int hashCode() {
            return Objects.hash(getR(), getC());
        }

    }

2. 下面是算法实现：
     方法有一个参数二维数组graph，即字符图。
     集合exists用于保存已经遍历过的字符。首先是两层循环（多个八连块），遍历到某一字符时，如果该字符为“@”且未遍历过（则意味着新的八连块出现），则以当前节点为根进行DFS，这里声明了一个栈，根节点首先入栈，并加入exists中，然后判断其周围是否有符合条件的字符，有则入栈并继续进行DFS，否则执行出栈，最后直至栈为空，则当前的一个八连块完毕，继续下一个八连块，直至整个图都遍历完毕，程序最后返回图中八连块的个数。

    /**
     * @param graph 图
     * @return 八连块个数
     */
    private int solver1(char[][] graph){
        if(graph == null){
            return 0;
        }
        Set<Dot> exists = new HashSet<>();
        int rnum = graph.length;
        int cNum = graph[0].length;
        int count = 0;

        for(int i = 0;i<rnum;i++){
            for(int j = 0;j<cNum;j++){
                Dot dot = new Dot(i,j);
                if(graph[i][j] == '@' && !exists.contains(dot)){
                    Stack<Dot> stack = new Stack<>();
                    stack.push(dot);
                    exists.add(dot);
                    while(!stack.isEmpty()){
                        Dot cur = stack.peek();
                        int r1 = Math.max(0, cur.getR()-1);
                        int r2 = Math.min(cur.getR()+1, rnum-1);
                        int c1 = Math.max(0, cur.getC() - 1);
                        int c2 = Math.min(cur.getC()+1, cNum-1);
                        /* flag：当存在相邻且未遍历的字符“@”时，需要跳出循环*/
                        boolean flag = false;
                        for(int r = r1;r<=r2;r++){
                            for(int c = c1;c<=c2;c++){
                                Dot d = new Dot(r,c);
                                if(graph[r][c] == '@' && !exists.contains(d)){
                                    stack.push(d);
                                    exists.add(d);
                                    flag = true;
                                    break;
                                }
                            }
                            if(flag){
                                break;
                            }
                        }
                        /* 如果不存在相邻且未遍历的@字符，则出栈 */
                        if(cur == stack.peek()){
                            stack.pop();
                        }
                    }
                    count++;
                }
            }
        }
        return count;
    }

解法二

  基于递归的DFS，对于当前节点，首先判断是否越界，是否为“@”，是否已经遍历过，否则符合条件，标记当前节点属于哪个八连块（这里二维数组exists用于记录节点属于哪个八连块），然后判断周围字符。

    /**
     *
     * @param graph 图
     * @param r 字符纵坐标
     * @param c 字符横坐标
     * @param id 八连块序号
     * @param exists 判断是否已经遍历过
     */
    private void solver2(char[][] graph, int r, int c, int id, int[][] exists){
        if(r<0 || c<0 || r>=graph.length || c>=graph[0].length){
            return ;
        }
        if(exists[r][c] != 0 || !(graph[r][c]=='@')){
            return;
        }
        exists[r][c] = id;
        for(int i  = -1;i<2;i++){
            for(int j = -1;j<2;j++){
                if(i != 0 || j != 0){
                    solver2(graph, r+i, c+j, id, exists);
                }
            }
        }
    }

辅助输入输出的代码如下所示：

public class OilDeposits {
	private int solver1(char[][] graph){{/*代码在上面*/}
	private void dfs(char[][] graph, int r, int c, int id, int[][] exists){/*代码在上面*/}
	public void solution(char[][] graph){
        System.out.println("解法一：" + solver1(graph));


        int[][] exists = new int[graph.length][graph[0].length];
        int count = 0;
        for(int i = 0;i<graph.length;i++){
            for(int j = 0;j<graph[0].length;j++){
                if(graph[i][j] == '@' && exists[i][j] == 0){
                    solver2(graph, i, j, ++count, exists);
                }
            }
        }
        System.out.println("解法二：" + count);
    }
    public static void main(String[] args){
        char graph[][] = {
                {'*','*','*','*','*','@',},
                {'*','*','@','@','*','@',},
                {'*','*','@','*','*','@',},
                {'@','@','@','*','*','@',},
                {'*','*','@','*','*','@',},
                {'*','*','*','*','*','@',},
                {'*','*','@','@','*','@',},};
        OilDeposits oilDeposits = new OilDeposits();
        oilDeposits.solution(graph);
    }
}