使用并查集查找无向图回路

一步步的教你使用并查集查找无向图回路

一、并查集的操作

1、查找（find）：确定元素属于哪个集合

2、合并（union）：将两个集合归并成一个集合

二、查找、合并操作代码

1、查找操作 代码

public int find(int x, int[] find) {
    if (find[x] < 0)
        return x;
    else
        return find(find[x], find);
}

2、合并操作 代码

public void union(int root1, int root2, int[] find) {
    find[root1] = root2;
}

三、 实例讲解#

1、准备工作

1、初始化

1、在无向图中存在几个顶点，就开辟一个长度为顶点数量大小的数组， 并初始化为 -1，数组记为 trance

2、find 函数的作用

1、 若此时 trance 数组为图示状态，先不用计较该数组是如何得到的，只需要知道 find 函数的执行流程，下边会介绍如何构建 trance 数组

2、find 函数的执行过程

对 3 调用 find 函数

搜索 trance[3],
由于 trance[3] = 2,
搜索 trance[2],
由于 trance[2] = 1,
搜索 trance[1],
由于 trance[1] = 0,
搜索 trance[0],
由于 trance[0] = -1,
此时返回 0

对 5 调用 find 函数

搜索 trance[5],
由于 trance[5] = 4,
搜索 trance[4],
由于 trance[4] = 1,
此时返回 4

这就是整个 find 的函数的执行流程

2、union 函数的作用

union 函数非常简单，传入两个参数 root1, root2

让第一个参数作为数组 trance 的下标，让第二个参数作为第一个参数对应下标的值
例如 root1 = 3, root2 = 5
则有 trance[3] = 5

例如 例如 root1 = 0, root2 = 2
则 trance[0] = 2

3、如何判断是否存在回路

存在一条边 side，该边有两个顶点 a，b(find 函数的详细过程请看上面 2、find 函数的作用)

若

使用 a 调用 find 函数返回 num1 >= 0
使用 b 调用 find 函数返回 num2 >= 0
当 num1 与 num2 相等时，证明若把 side 边纳入到 trance 数组中时，
会出现回路，因此此时不要将 side 边纳入到 trance 数组中

示例：

此时 trance 数组为图示状态，先不用计较该数组是如何得到的，

只需要知道如何判断回路就可以，下边会介绍如何构建 trance 数组

存在一条边 side，该边有两个顶点 3，5

使用 2 调用 find 函数 trance[3] = 2
                     trance[2] = 1
                     trance[1] = 0
                     trance[0] = 4
                     trance[4] = -1
                     所以 num1 = 4 >= 0

使用 5 调用 find 函数 trance[5] = 4
                     trance[4] = -1
                     所以 num2 = 4 >= 0
                    由于 num1 = num2,所以在该有无图中存在回路
                    不会将边 side 纳入到 trance 数组中

2、使用并查集判断下图所示的无向图中是否存在回路

下面将通过实例讲解 trance 数组是如何构建的

1、初始化

由于在图示中存在 4 个顶点，所以初始化一个长度为 4 的数组，数组记为 trance，

并初始化为 -1

数组的初始状态如图所示

2、将边 a 纳入到 trance 数组

此时数组 trance 的状态如图

边 a 有 0， 1 顶点
对 0 调用 find 函数    tranc[0] = -1
                    所以 num1 = 0 >= 0

对 1 调用 find 函数    tranc[1] = -1
                    所以 num2 = 1 >= 0

此时使用 num1 和 num2 调用 union 函数 (这里可以看 2、union 函数的作用 上方黑体字部分)
                    有 trance[0] = 1

2、将边 b 纳入到 trance 数组

此时数组 trance 的状态如图

边 b 有 0， 2 顶点
对 0 调用 find 函数    tranc[0] = 1
                    tranc[1] = -1
                    所以 num1 = 1 >= 0

对 2 调用 find 函数 tranc[2] = -1
                    所以 num2 = 2 >= 0

此时使用 num1 和 num2 调用 union 函数
                    有 trance[1] = 2

3、将边 c 纳入到 trance 数组

此时数组 trance 的状态如图

边 c 有 0， 3 顶点
对 0 调用 find 函数    tranc[0] = 1
                    tranc[1] = 2
                    trance[2] = -1
                    所以 num1 = 2 >= 0

对 3 调用 find 函数 tranc[3] = -1
                    所以 num2 = 3 >= 0

此时使用 num1 和 num2 调用 union 函数
                    有 trance[2] = 3

4、将边 d 纳入到 trance 数组

此时数组 trance 的状态如图

边 d 有 1， 2 顶点
对 1 调用 find 函数    tranc[1] = 2
                    tranc[2] = 3
                    trance[3] = -1
                    所以 num1 = 3 >= 0

对 2 调用 find 函数    tranc[2] = 3
                    tranc[3] = -1
                    所以 num2 = 3 >= 0

此时 num1 = num2 存在回路，就不向 trance 中纳入边 d，此时 trance 数组不发生变化

5、将边 e 纳入到 trance 数组

此时数组 trance 的状态如图

边 e 有 1， 3 顶点
对 1 调用 find 函数    tranc[1] = 2
                    tranc[2] = 3
                    trance[3] = -1
                    所以 num1 = 3 >= 0

对 3 调用 find 函数    tranc[3] = -1
                    所以 num2 = 3 >= 0

此时 num1 = num2 存在回路，就不向 trance 中纳入边 e，此时 trance 数组不发生变化

6、将边 f 纳入到 trance 数组

此时数组 trance 的状态如图

边 f 有 2， 3 顶点
对 2 调用 find 函数    tranc[2] = 3
                    trance[3] = -1
                    所以 num1 = 3 >= 0

对 3 调用 find 函数    tranc[3] = -1
                    所以 num2 = 3 >= 0

此时 num1 = num2 存在回路，就不向 trance 中纳入边 e，此时 trance 数组不发生变化

四、完整代码

package other;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 并查集
 */
public class UnionFindSet {

    public static void main(String[] args) {
        UnionFindSet unionFindSet = new UnionFindSet();
        int[] trance = new int[4];
        List<String> list = new ArrayList<>();
        list.add("0-1");
        list.add("0-2");
        list.add("0-3");
        list.add("1-2");
        list.add("1-3");
        list.add("2-3");

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

        for (String s : list) {
            System.out.println(Arrays.toString(trance));
            String[] split = s.split("-");
            int find1 = unionFindSet.find(Integer.parseInt(split[0]), trance);
            int find2 = unionFindSet.find(Integer.parseInt(split[1]), trance);
            if (find1 != find2) {
                unionFindSet.union(find1, find2, trance);
            }
        }
    }

    public int find(int x, int[] trance) {
        if (trance[x] < 0)
            return x;
        else
            return find(trance[x], trance);
    }

    public void union(int root1, int root2, int[] trance) {
        trance[root1] = root2;//将root1作为root2的新树根
    }
}

打赏