并查集(例子+画图+Code详细解析) 并查集

发表于

并查集

「这是我参与11月更文挑战的第8天，活动详情查看：2021最后一次更文挑战」

什么是并查集

举个例子简单理解，就是相同血缘的人组成了一个个家族（不考虑家庭伦理剧！）

  1. 两个人都没有家族但是血缘相同，那么他们俩成立一个家族

image.png

  1. 如果某人和某个家族的人有血缘关系，就把他加入该家族

image.png

  1. 如果我们发现两个不同家族的人有人血缘相同，就把两个家族合并为一个家族

image.png
最后得到的情况是，各个家族真的没有血缘关系了

总结下来并查集就是：

  1. 并查集可以进行集合合并的操作（并）
  2. 并查集可以查找元素在哪个集合中（查）
  3. 并查集维护的是一堆集合（集）

根据具体场景深入理解

上述例子只是有了初步的理解，具体怎么使用和如何考虑，可以在下面的例子中更有效的学习。

背景介绍

冗余连接

树可以看成是一个连通且无环的无向图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。

图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。

image.png

输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]


输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]

题目分析

一共有n个点n条边，如果没有环的情况下应该仅有n-1条边才对

我们的任务是删除一条边，但不会让任何点孤立，失去联系

可以考虑按边出现次序依次选择，对每条边上的两个点，设为A,B进行分析

其情况有以下三种：

  1. 两个点都没有本访问过，那么我们就让A作为父亲节点，B作为子节点，AB构成了一颗树
    并将点AB访问情况设置为true
  2. 有一个节点被访问过，例如B节点被访问过，A节点没有被访问过
    那么B节点可能是一个树的根，叶子节点或者中间节点，但无论哪一种只需要让A的父亲为B即可，这样A也属于B家族的一个成员了
    并将B设置为ture
  3. A,B都被访问过

（1）我们首先查找A和B节点的根节点，他们俩是不是一个家族的，如果是一个家族的说明他们俩已经被链接起来了，那么这一条边便是多余的

根据本题只会有一条多余的边，因此返回这一条即可啦

（2）如果A和B家族不一样，那么我们将A和B两大家族合并即可，我们可以把B家族的族长也就是根结点并入到A节点，或者A节点的族长之下即可

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
ini复制代码    public int[] findRedundantConnection(int[][] edges) {
        boolean[] visited=new boolean[edges.length+1];//创建n长度大小的数组，用来记录节点是否被访问过了
        HashMap<Integer,Integer>map=new HashMap<>();//我们不用单独创建树结构，用mao数组保存 孩子索引和父亲索引即可
        for (int i = 0; i < edges.length; i++) {
            int a=edges[i][0];
            int b=edges[i][1];
            if(visited[a]==false&&visited[b]==false){//两者都没有归属
                map.put(b,a);//让a当b的父节点
                map.put(a,-1);//设a的父节点为-1，用来判断到头了
                visited[a]=true;
                visited[b]=true;
            }else if(visited[a]==false){
                map.put(a,b);
                visited[a]=true;
            }else if(visited[b]==false){
                map.put(b,a);
                visited[b]=true;
            }else {
                int rootOfA=getRoot(a,map);
                int rootOfB=getRoot(b,map);
                if(rootOfA==rootOfB)return edges[i];
                map.put(rootOfB,rootOfA);//让a当b的父节点
            }
        }
        return null;
    }
    public int getRoot(int cur,HashMap<Integer,Integer>map){
        if(map.get(cur)==-1)return cur;
        return getRoot(map.get(cur),map);
    }

并查集的经典案例-克鲁斯卡尔算法

克鲁斯卡尔算法简介

克鲁斯卡尔算法是一种用来寻找最小生成树的算法（用来求加权连通图的最小生成树的算法）。在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。

具体的操作过程为：

  1. 将图的所有连接线去掉，只剩顶点
  2. 从图的边集数组中找到权值最小的边，将边的两个顶点连接起来
  3. 继续寻找权值最小的边，将两个顶点之间连接起来，如果选择的边使得最小生成树出现了环路，则放弃该边，选择权值次小的边
  4. 直到所有的顶点都被连接在一起并且没有环路，最小生成树就生成了。

两个核心问题

问题一 对图的所有边按照权值大小进行排序。

直接采用排序算法进行排序即可，或者构建最小堆，也是不错的选择。

问题二 将边添加到最小生成树中时，怎么样判断是否形成了回路。

核心思想是记录处理，运用了并查集的处理思想

处理方式是：记录顶点在”最小生成树”中的终点，顶点的终点是”在最小生成树中与它连通的最大顶点”。然后每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。

完整版代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
arduino复制代码import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;


class Edge implements Comparable<Edge> {
    //起始点
    private int begin;
    //终止点
    private int end;
    //权值
    private int weight;

    public Edge(int begin, int end, int weight) {
        this.begin = begin;
        this.end = end;
        this.weight = weight;
    }

    public int getBegin() {
        return begin;
    }

    public void setBegin(int begin) {
        this.begin = begin;
    }

    public int getEnd() {
        return end;
    }

    public void setEnd(int end) {
        this.end = end;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge o) {
        if (o.weight > this.weight) {
            return -1;
        } else {
            return 1;
        }
    }
}

public class Kruskal {

    public static void main(String[] args) {
        //默认以a为根节点的最小生成树
        List<Edge> list = new ArrayList<>();
        int[][] arr = new int[][]{
                {-1, 4, 0, 0, 0, 0, 0, 8, 0},
                {0, -1, 8, 0, 0, 0, 0, 11, 0},
                {0, 0, -1, 7, 0, 4, 0, 0, 2},
                {0, 0, 0, -1, 9, 14, 0, 0, 0},
                {0, 0, 0, 0, -1, 10, 0, 0, 0},
                {0, 0, 0, 0, 0, -1, 2, 0, 0},
                {0, 0, 0, 0, 0, 0, -1, 1, 6},
                {0, 0, 0, 0, 0, 0, 0, -1, 7},
                {0, 0, 0, 0, 0, 0, 0, 0, -1}
        };
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i][j] > 0) {
                    list.add(new Edge(i, j, arr[i][j]));
                }
            }
        }
        Collections.sort(list);
        //数组中每一个节点都只知道他的父节点是什么，-1表示不存在父节点，0位置是根节点
        int[] parent = new int[arr.length];
        for (int i = 1; i < arr.length; i++) {
            parent[i] = -1;
        }
        int m = 0, n = 0;
        for (Edge edge : list) {
            //寻找这两个点有没有相同的父节点
            m = find(parent, edge.getBegin());
            n = find(parent, edge.getEnd());
            if (m != n ) {
                parent[m] = n;
                System.out.println("加入边（"+edge.getBegin()+","+edge.getEnd()+") 权重 "+ edge.getWeight());
            }
        }
        System.out.println(Arrays.toString(parent));
    }

    private static int find(int[] parent, int ch) {
        while (parent[ch] > 0) {
            ch = parent[ch];
        }
        return ch;
    }
}

代码结果输出

1
2
3
4
5
6
7
8
9
10
11
csharp复制代码加入边（6,7) 权重 1
加入边（2,8) 权重 2
加入边（5,6) 权重 2
加入边（0,1) 权重 4
加入边（2,5) 权重 4
加入边（2,3) 权重 7
加入边（0,7) 权重 8
加入边（3,4) 权重 9
[1, 3, 8, 4, -1, 7, 7, 3, 7]

Process finished with exit code 0

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%