[数据结构与算法]并查集结构和岛问题

如有1、2、3、4、5个节点，它们的指针分别指向自身，如要将2节点放在1结点之后，则2的指针指向1节点。如何确定多个元素是否在同一个结合中。则查询该节点的头节点，如头节点相同，则在同一个结合中。实现结合融合时，将节点数少的集合的头结点指向节点数多的头节点。（多链表结构）

优化：查询结点（A）的头节点时将该节点到头节点的节点分别指向头节点。

岛问题：一个矩阵只有0和1两种结构，每个位置都可以和自己的上下左右相连，如果一片1连在一起，这部分叫一个岛，求一个矩阵有多少个岛。

1 1 0 0 1 0 0

0 0 1 1 1 1 0

1 0 0 0 0 0 1

递归递归单线程思路：遍历整个矩阵，到每一次遇到1时，进入一个递归函数中，该递归函数将该该元素及其上下左右是1的元素改为2或其他。（注意边界问题）

public class BCJ {


    public static void creatArr() {
        // 生成长度随机的数组
        int[][] arr = new int[3][];
        arr[0] = new int[3];
        arr[1] = new int[3];
        arr[2] = new int[3];
        arr[0][0] = 1;
        arr[0][1] = 1;
        arr[0][2] = 0;
                      
        arr[1][0] = 0;
        arr[1][1] = 0;
        arr[1][2] = 1;

        arr[2][0] = 1;
        arr[2][1] = 0;
        arr[2][2] = 0;


        int nUmber = getNUmber(arr);
        System.out.println(nUmber);
    }


    public static int getNUmber(int[][] arr) {
        int num = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int i1 = 0; i1 < arr[i].length; i1++) {
                if (arr[i][i1] == 1) {
                    ++num;
                    getPro(arr, i, i1, arr[i].length, arr.length);
                }
            }

        }

        return num;
    }


    public static void getPro(int[][] arr, int x, int y, int width, int height) {
        if (x < 0 || x >= width || y < 0 || y >= height) {
            return;
        }
        if (arr[x][y] != 1) {
            return;
        }
        arr[x][y] = 2;
        getPro(arr, x - 1, y, width, height);
        getPro(arr, x + 1, y, width, height);
        getPro(arr, x, y - 1, width, height);
        getPro(arr, x, y + 1, width, height);
    }

    public static void main(String[] args) {
        creatArr();
    }
}

并查集方法

将矩阵分成多个区域，将每个区域的连续出现1的区域放在一个集合中，然后再将每个区域的边界与其他集合合并。