[聊聊算法]并查集原理及实战

Posted on 2023年1月27日 by luozhiyun

这档专栏打算整理一些比较容易归纳总结的模板题,让这些知识点不仅仅是我的笔记,希望也能帮助到大家

并查集主要用于解决一些元素分组的问题，它主要支持两种操作：

查询：查询某个元素属于哪个集合，通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。
合并：将两个集合合并为一个。

这题来计算有几个省份，如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连，这些相连的城市构成一个省份。所以这题就是一个很好的模板题，需要将相关联的城市合并，然后找出共有几个分组。

比如我们现在有0，1，2，3，4，5，6，7这8个城市，0、1、2、3这三个城市有关联可以归结为一个省，5、6、7这三个城市有关联也是一个省，4单独就是一个省。

所以下面我们看看并查集怎么进行添加、查询、合并的操作。

一开始，我们先将它们的父节点设为自己，用数组 fa 来保存节点之间的关联关系。

var fa []int
func initF(n int) {
    fa = make([]int, n)
    for i:=0;i<n;i++{
        fa[i] = i
    }
}

查询操作主要是找到该节点的根节点，因为要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。

func find(x int) int {
    if fa[x] == x {
        return x
    }else {
        return find(fa[x]) //一层一层访问父节点，直至根节点
    }
}

func merge(i ,j int) {
    fa[find(i)] = find(j)
}

先找到两个集合的代表元素，然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者。

并查集的应用

所以我们回到这题：剑指 Offer II 116. 省份数量

这题中给了一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。那么我们需要从这个矩阵里面构建我们的并查集。

城市的数量其实就是矩阵的长度，这个长度决定了我们上面提到的并查集 fa 数组，我们只需要遍历 isConnected 数据，然后将有关联的城市都合并到一起，最后看看有几个父节点，就可以知道有多少个省份了。

func findCircleNum(isConnected [][]int) int {
    initF(len(isConnected))

    for i:= 0;i<len(isConnected);i++{
        for j:=0;j<len(isConnected[i]);j++{
            if isConnected[i][j] == 1{
                fi := find(i)
                fj := find(j)
                // 已经是同一个父节点,那么不需要合并
                if fi == fj {
                    continue
                }
                // 不是同一个父节点，需要合并
                merge(i,j) 
            }
        }
    }
    ret := 0
    for i:=0;i<len(fa);i++{
        if fa[i] == i {
            ret ++
        }
    } 
    return ret
}

var fa []int
func initF(n int) {
    fa = make([]int, n)
    for i:=0;i<n;i++{
        fa[i] = i
    }
}

func find(x int) int {
    if fa[x] == x {
        return x
    }else {
        return find(fa[x]) //一层一层访问父节点，直至根节点
    }
}

func merge(i ,j int) {
    fa[find(i)] = find(j)
}

但是上面的做法在性能上有一点点问题，因为我们在父子节点合并的时候，可能会形成一个很长的链表，随着链越来越长，我们想要从底部找到根节点会变得越来越难。

比如下面，一开始只有两个节点，后面添加到4个节点的时候，链表也越来越长：

所以我们可以使用路径压缩的方法。既然我们只关心一个元素对应的根节点，那么在查找的时候把沿途的每个节点的父节点都设为根节点即可。

func find(x int) int {
    if fa[x] == x {
        return x
    }else {
        fa[x] = find(fa[x])//父节点设为根节点
        return fa[x]       //返回父节点
    }
}

剑指 Offer II 117. 相似的字符串

这题是判断strs 中有多少个相似字符串组，那么这就是一题需要解决元素分组的问题，所以我们可以考虑并查集。

如果用并查集，那还是用我们上面的套路模板，没有任何区别，唯一不同的是这题我们需要判断两个单词相似了才可以加为同一集合。并且题目中说了列表中的每个字符串都是 strs 中其它所有字符串的一个 字母异位词 ，所以在解题的时候不需要判断相似，只需要判断单词位置是否变了一次以上。

func numSimilarGroups(strs []string) int { 
    initF(len(strs))
    for i:=0;i<len(strs);i++{
        for j:= i+1 ;j<len(strs) ;j++{
            fi := find(i)
            fj := find(j)
            if fi == fj {
                continue
            }
            if check(strs[i], strs[j]) {
                f[fi] = fj
            }
        }
    }
    ret :=0 
    for i:=0;i<len(f);i++{
        if f[i] == i {
            ret++
        }
    }
    return ret
}

var f []int
func initF(n int) {
    f = make([]int, n)
    for i:=0;i<len(f);i++{
        f[i] = i
    }
}

func find(x int) int {
    if f[x] == x {
        return x
    }else {
        f[x] = find(f[x]) //路径压缩
        return  f[x]
    }
}

func check(a,b string) bool {//判断是否相似
    num :=0 
    for i:=0; i<len(a) && i<len(b); i++{
        if a[i]!=b[i] {
            num++
            if num>2 {
                return false
            }
        }
    }
    return true
}

剑指 Offer II 118. 多余的边

这题是让我们找出一条可以删去的边，删除后让这个图可以变成一个树。

以题中 edges = [[1,2],[1,3],[2,3]] 为例，最开始 3 个节点都是离散的，任何两个节点之间都不存在边连接，也就是说是 3 个子图，如图(a)所示。

先在图内添加一条边 [1,2]，于是节点 1 和节点 2 所在子图连在一块形成新的子图，如图(b)所示。

接下来添加边 [1,3] ,于是节点 1 和节点 3 所在子图连在一块形成新的子图，如图(c)所示。

最后添加边 [2,3]，因为节点 2 和节点 3 原本就属于同一个子图，此时再相连就会形成环。

所以在添加一条边时若两个节点原本就属于同一个子图就会形成环。那么其实就是判断两个子图是否属于同一个子图，并把子图都合并起来，这使用并查集就可以解决问题。

 func findRedundantConnection(edges [][]int) []int {

    initF(len(edges)+1) //因为元素是从1开始的
    ret := -1
    for i:=0;i<len(edges);i++{
        l1 := find(edges[i][0])
        l2 := find(edges[i][1])
        //edges[i]下面的必然是同一个组的
        //父节点不相同，说明需要合并
        if l1!=l2 { 
            f[l1] = l2
        //说明这两个元素已经构成过组，合并过，那么再合并就会存在环
        }else {
            ret = i
            break //因为只需找出一条边，所以到这里已经找完，直接返回即可
        }
    }
    return edges[ret]
}

var f []int
func initF(n int) {
    f = make([]int, n)
    for i:=0;i<len(f);i++{
        f[i] = i
    }
}

func find(i int) int{
    if f[i] == i {
        return i
    }else {
        f[i] = find(f[i])
        return f[i]
    }
}

通过上面的一些例子可以发现并查集的题其实非常的 “模板”，基本上就是初始化、find 父节点、合并、最后判断有多个个集合。最有可能有区别的地址就是在合并的时候，我们需要判断两个元素为什么是同一集合才能将其合并。