并查集

作者: bangbang2 | 来源:发表于2020-07-11 21:29 被阅读0次

首先,并查集是树状结构
查:确定元素属于哪一个集合,看图

image.png
查的一般代码写法:
查的基本思路:如果是根节点,直接返回该节点的值,否则递归该函数,参数为该节点的父节点,就是去找父节点是什么,结合图,代表一层一层向上走
int find(int parent[], int i) {
        if (parent[i] == -1)//如果i的父节点是-1,就代表该节点是根节点
            return i;
        return find(parent, parent[i]);//如果不是根节点,就返回该节点的父节点的父节点,///不断向上递归,如图所示
    }

并:将两个子集合并为一个集合,看图


image.png

基本思路:
先找这两个节点所属于的根节点,判断这两个根节点是否,不相等,代表不是一个集合,需要进行合并,就将xset这个根节点,指向yset这个根节点,xset作为一颗子树,如图所示

void union(int parent[], int x, int y) {
        int xset = find(parent, x);//找x的根节点
        int yset = find(parent, y);
        if (xset != yset)//不相等,代表不是一个集合,需要进行合并,就将xset这个根节点,指向yset这个根节点,xset作为一颗子树,如图所示
            parent[xset] = yset;
    }

路径压缩


image.png

如上图所示,如果像查那样一层一层的找父节点,最后的目的是确定根节点,但是如果树很高,这样找的话就太慢了,我们直接将所有节点都接到根节点,这样一步到位,效率很高啊
其实只改一行,改最后的返回值,如果不是根节点,不返回上一层节点,直接返回根节点

int find(int x) {
  if (x != fa[x])  // x不是自身的父亲,即x不是该集合的代表
    fa[x] = find(fa[x]);  // 查找x的祖先直到找到代表,于是顺手路径压缩
  return fa[x];
}

举例,例如之前做的朋友圈那个题


image.png

parent[i]存的是i节点的父节点

public class Solution {
    int find(int parent[], int i) {
        if (parent[i] == -1)//如果一个节点的父节点是-1,就代表该节点是该树的根节点
            return i;
        return find(parent, parent[i]);
    }

    void union(int parent[], int x, int y) {
        int xset = find(parent, x);
        int yset = find(parent, y);
        if (xset != yset)
            parent[xset] = yset;
    }
    public int findCircleNum(int[][] M) {
        int[] parent = new int[M.length];
        Arrays.fill(parent, -1);//初始化都为独立的根节点,为-1
        for (int i = 0; i < M.length; i++) {
            for (int j = 0; j < M.length; j++) {//遍历矩阵
                if (M[i][j] == 1 && i != j) {//如果其中两个节点相连,就合并这两个子集
                    union(parent, i, j);
                }
            }
        }
        int count = 0;
        for (int i = 0; i < parent.length; i++) {//遍历parent数组,出现-1
//就代表是根节点,就代表是一个连通分量
            if (parent[i] == -1)
                count++;
        }
        return count;
    }
}

相关文章

  • markdown学习

    #并查集 ##并查集的定义 ##并查集的操作

  • 算法模板(四)并查集

    并查集 路径压缩并查集

  • 并查集入门使用

    本文参考自《算法笔记》并查集篇 并查集的定义 什么是并查集?并查集可以理解为是一种维护数据集合的结构。名字中并查集...

  • 并查集练习

    并查集 参考《算法笔记》 三要素:并,查,集。 并差集与一个算法有关,kruskal算法,就可通过并查集实现。 1...

  • 并查集

    并查集 并查集是什么 并查集是一种用来管理元素分组情况的数据结构,并查集可以高效地进行如下操作: 查询元素a和元素...

  • 数据结构与算法(十二)并查集(Union Find)

    本文主要包括以下内容: 并查集的概念 并查集的操作 并查集的实现和优化Quick FindQuick Union基...

  • 并查集

    并查集是什么 并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作。不过需要注意并查集虽然可以...

  • 并查集

    开始时让每个元素构成一个个单元素集合(注意初始化时应使每个元素各成一组)按照一定顺序将属于同一组元素所在的集合合并...

  • 并查集

  • 并查集

    并查集 https://blog.csdn.net/liujian20150808/article/details...

网友评论

      本文标题:并查集

      本文链接:https://www.haomeiwen.com/subject/fyqwcktx.html