图论系列（1）——并查集介绍

前言：

最近笔试面试碰到好几道与连通图有关的题目，正好从这些题抛砖引玉，好好看看应该怎么处理这方面的问题。

问题描述：

假如已知有n个人和m对好友关系（存于数字r）。如果两个人是直接或间接的好友（好友的好友的好友…），

则认为他们属于同一个朋友圈，

请写程序求出这n个人里一共有多少个朋友圈。

假如：n = 5， m = 3， r = {{1 , 2} , {2 , 3} ,{4 , 5}}，表示有5个人，1和2是好友，2和3是好友，4和5是好友，

则1、2、3属于一个朋友圈，4、5属于另一个朋友圈，结果为2个朋友圈。

最后请分析所写代码的时间、空间复杂度。评分会参考代码的正确性和效率。

解法1（时间复杂度O(N^2)）：

对每个节点都尝试进行dfs遍历，获得每点对应的最大连通图， 使用marked数组标记该节点是否被访问。

public class Main {

    public static void main(String[] args) {

        int M = 5;
        int[][] graph = new int[M][M];
        int[][] edges = {{1, 2}, {2, 3}, {4, 5}};

        for (int i = 0; i < edges.length; i ++) {
            graph[edges[i][0] - 1][edges[i][1] - 1] = 1;
            graph[edges[i][1] - 1][edges[i][0] - 1] = 1;
        }

        // 输出图
        for (int i = 0; i < M; i ++) {
            for (int j = 0; j < M; j ++) {
                System.out.print(graph[i][j] + " ");
            }
            System.out.println("");
        }

        List<String> res = new ArrayList<String>();

        originSolver(graph, new boolean[M], res, M);

        System.out.println("");
        System.out.println("result group: ");
        for (String s : res) {
            System.out.println(s);
        }

    }

    public static void originSolver(int[][] graph, boolean[] marked, List<String> res, int M) {

        for (int i = 0; i < M; i ++) {

            if (marked[i]) continue;

            res.add(getGroup(graph, marked, M, i));

        }
    }

    // 对潜在组的成员进行dfs遍历
    public static String getGroup(int[][] graph, boolean[] marked, int M, int row) {

        if (marked[row]) return "";

        String tmp = row + " ";
        marked[row] = true;

        for (int i = 0; i < M; i ++) {
            if (graph[row][i] == 1) tmp += getGroup(graph, marked, M, i);
        }

        return tmp;
    }

}

输出结果：

0 1 0 0 0 
1 0 1 0 0 
0 1 0 0 0 
0 0 0 0 1 
0 0 0 1 0 

result group: 
0 1 2 
3 4 

解法2（引入并查集）：

并查集是一种数据结构，主要分为三大部分：

1. 保存集合信息的数组
2. 查找对应元素的集合id的find函数
3. 合并两个集合的union函数

union函数的时间复杂度O(N)，查找find函数时间复杂度O(1)。

public class Main {

    public static void main(String[] args) {

        int M = 5;
        UnionFind uf = new UnionFind(M + 1);
        int[][] edges = {{1, 2}, {2, 3}, {4, 5}};

        // 合并操作
        for (int i = 0; i < edges.length; i ++) {
            uf.union(edges[i][0], edges[i][1]);
        }

        // 输出图
        for (int i = 1; i <= M; i ++) {
            System.out.println("index: " + i + "; group: " + uf.groupId[i]);
        }

    }

    static class UnionFind {

        int[] groupId;

        public UnionFind(int n) {

            groupId = new int[n];

            for (int i = 0; i < n; i ++) {
                groupId[i] = i;
            }
        }

        // 寻找元素对应的集合
        public int find(int element) {

            return groupId[element];

        }

        // 查找两个元素是否连接
        public boolean isConnected(int firstElment, int secondElement) {
            return find(firstElment) == find(secondElement);
        }

        // 合并两个集合
        public void union(int firstElement, int secondElement) {

            int firstGroup = find(firstElement);
            int secondGroup = find(secondElement);

            // 不是一个集合，进行合并操作
            if (firstGroup != secondGroup) {

                for (int i = 0; i < groupId.length; i++) {
                    if (groupId[i] == secondGroup) groupId[i] = firstGroup;
                }

            }

        }
    }
}

输出结果：

index: 1; group: 1
index: 2; group: 1
index: 3; group: 1
index: 4; group: 4
index: 5; group: 4

解法2（union操作优化）：

我们如果在groupId数组中不保存节点的集合号，而转为保存元素的上级元素，union操作的时间复杂度将会得到极大的减少，不再是O(N)，而是变为O(M) + O(K)，K, M为当前两个子树的高度。

但是相应的代价就是find函数的时间复杂度变大了，和查询的子树高度正相关。

public class Main {

    public static void main(String[] args) {

        int M = 5;
        UnionFind uf = new UnionFind(M + 1);
        int[][] edges = {{1, 2}, {2, 3}, {4, 5}};

        // 合并操作
        for (int i = 0; i < edges.length; i ++) {
            uf.union(edges[i][0], edges[i][1]);
        }

        // 输出图
        for (int i = 1; i <= M; i ++) {
            System.out.println("index: " + i
                    + "; parent: " + uf.groupId[i]
                    + "; group: " + uf.find(i));
        }

    }

    static class UnionFind {

        // 保存parent信息
        int[] groupId;

        public UnionFind(int n) {

            groupId = new int[n];

            for (int i = 0; i < n; i ++) {
                groupId[i] = -1;
            }
        }

        // 寻找元素对应的集合
        public int find(int element) {
            while (groupId[element] >= 0) {
                element = groupId[element];
            }

            return element;
        }

        // 查找两个元素是否连接
        public boolean isConnected(int firstElment, int secondElement) {
            return find(firstElment) == find(secondElement);
        }

        // 合并两个集合
        public void union(int firstElement, int secondElement) {

            int firstGroup = find(firstElement);
            int secondGroup = find(secondElement);

            // 不是一个集合，进行合并操作
            if (firstGroup != secondGroup) {
                groupId[secondElement] = firstElement;
            }

        }
    }
}

输出结果：

index: 1; parent: -1; group: 1
index: 2; parent: 1; group: 1
index: 3; parent: 2; group: 1
index: 4; parent: -1; group: 4
index: 5; parent: 4; group: 4

解法3（union操作基于重量合并）：

为了提高find函数的性能，使用基于重量进行合并，重量指的是集合的节点数。

public class Main {

    public static void main(String[] args) {

        int M = 5;
        UnionFind uf = new UnionFind(M + 1);
        int[][] edges = {{1, 2}, {2, 3}, {4, 5}};

        // 合并操作
        for (int i = 0; i < edges.length; i ++) {
            uf.union(edges[i][0], edges[i][1]);
        }

        // 输出图
        for (int i = 1; i <= M; i ++) {
            System.out.println("index: " + i
                    + "; parent: " + uf.groupId[i]
                    + "; group: " + uf.find(i)
                    + "; weight: " + uf.weights[i]);
        }

    }

    static class UnionFind {

        // 保存parent信息
        int[] groupId;
        int[] weights;

        public UnionFind(int n) {

            groupId = new int[n];
            weights = new int[n];

            for (int i = 0; i < n; i ++) {
                groupId[i] = -1;
                weights[i] = 1;
            }
        }

        // 寻找元素对应的集合
        public int find(int element) {
            while (groupId[element] >= 0) {
                element = groupId[element];
            }

            return element;
        }

        // 查找两个元素是否连接
        public boolean isConnected(int firstElment, int secondElement) {
            return find(firstElment) == find(secondElement);
        }

        // 合并两个集合
        public void union(int firstElement, int secondElement) {

            int firstGroup = find(firstElement);
            int secondGroup = find(secondElement);

            // 不是一个集合，进行合并操作
            if (firstGroup != secondGroup) {
                if (weights[firstElement] > weights[secondElement]) {
                    groupId[secondElement] = firstElement;
                    weights[firstElement] += weights[secondElement];
                } else {
                    groupId[firstElement] = secondElement;
                    weights[secondElement] += weights[firstElement];
                }
            }

        }
    }
}

输出结果：

index: 1; parent: 2; group: 2; weight: 1
index: 2; parent: -1; group: 2; weight: 3
index: 3; parent: 2; group: 2; weight: 1
index: 4; parent: 5; group: 5; weight: 1
index: 5; parent: -1; group: 5; weight: 2

解法4（union操作基于高度合并）：

使用高度合并可以限制union操作时生成集合树的高度。

需要处理两种情况：

1. 两个集合高度不相等的时候，取高度大的那个作为更新高度。
2. 两个集合高度相等的时候，最大高度加1（见下图）。

public class Main {

    public static void main(String[] args) {

        int M = 5;
        UnionFind uf = new UnionFind(M + 1);
        int[][] edges = {{1, 2}, {2, 3}, {4, 5}};

        // 合并操作
        for (int i = 0; i < edges.length; i ++) {
            uf.union(edges[i][0], edges[i][1]);
        }

        // 输出图
        for (int i = 1; i <= M; i ++) {
            System.out.println("index: " + i
                    + "; parent: " + uf.groupId[i]
                    + "; group: " + uf.find(i)
                    + "; height: " + uf.heights[i]);
        }

    }

    static class UnionFind {

        // 保存parent信息
        int[] groupId;
        int[] heights;

        public UnionFind(int n) {

            groupId = new int[n];
            heights = new int[n];

            for (int i = 0; i < n; i ++) {
                groupId[i] = -1;
                heights[i] = 1;
            }
        }

        // 寻找元素对应的集合
        public int find(int element) {
            while (groupId[element] >= 0) {
                element = groupId[element];
            }

            return element;
        }

        // 查找两个元素是否连接
        public boolean isConnected(int firstElment, int secondElement) {
            return find(firstElment) == find(secondElement);
        }

        // 合并两个集合
        public void union(int firstElement, int secondElement) {

            int firstGroup = find(firstElement);
            int secondGroup = find(secondElement);

            // 不是一个集合，进行合并操作
            if (firstGroup != secondGroup) {
                if (heights[firstElement] > heights[secondElement]) {
                    groupId[secondElement] = firstElement;
                } else if (heights[firstElement] < heights[secondElement]) {
                    groupId[firstElement] = secondElement;
                } else {
                    groupId[firstElement] = secondElement;
                    heights[secondElement] += 1;
                }
            }

        }
    }
}

输出结果：

index: 1; parent: 2; group: 2; height: 1
index: 2; parent: -1; group: 2; height: 2
index: 3; parent: 2; group: 2; height: 1
index: 4; parent: 5; group: 5; height: 1
index: 5; parent: -1; group: 5; height: 2