连通图问题 - 并查集

提出背景

在图论问题中,我们经常性遇到一些关于两个点是否连通的问题。
比如在最小生成树kruskal算法中,我们在逐渐选取最小边的时候,我们需要判断当前要选的边的两个顶点是否已经在同一连通块中。
有基础的同学都知道,在大多数图论问题中,我们的图都是通过邻接表或点对表示边而非邻接矩阵存储的,这样能够提高遍历和存储的时间和空间效率。但实际上,这两种方式也有一个严重的缺陷:不方便查询、修改指定的两点u和v的关系。于是在这种情况下的这两种方式构成的图的连通性也非常难以判断。
这时我们需要一种数据结构能够方便的维护查询图的连通性。

并查集基本概念及操作介绍

所谓并查集,其实是相互连通的各点通过父节点表示法构成的森林(很多棵树的集合),我们判断两点是否相互连通,实际上就是通过他们是否在同一棵树内。很显然同一棵树内的所有点相互连通,这个通过刚才的定义就可以显然得出了,并不需要证明(实际上这里给出的定义是我个人对并查集的理解)。
由上面所说的父节点表示法,并查集这种数据结构自然而然地就是只需要一个一维数组表示就行了,被没有多么麻烦。我们假设为f[i]表示节点i在并查集构成的森林中的父节点。f[i]的初始值设定为i本身
通常来讲,并查集有两种基本操作:

  1. 查询操作:查询当前点u的所在的并查集构成的树的根是哪个节点,具体代码实现为:
    int find(int x){
    if(x != f[x])
        return find(f[x]);//x == f[x]表示节点x即为本并查集的根
    return x;
    }
  2. 合并操作:将两个并查集(两个树)合并,其代表的是这两个连通块之间出现了一条连通边。我们只需要将这两个并查集的树的根进行合并即可,具体操作代码为:
    void merge(int u,int v){
    u = find(u);
    v = find(v);//分别寻找所在并查集的根
    f[v] = u;//f[u] = v也可以,通常来讲
    return;
    }

    这两项就是并查集的基本操作了。


并查集构造、查询方式的优化

上面的并查集虽然方便,但是还有时间复杂度(效率)问题。
可以注意到,find函数的时间复杂度是和递归层数,也就是当前点在并查集中的深度相关的,最坏情况下,查询一次的时间复杂度为O(n)(也就是这个树实际上是一个链的形状),这种效率是我们无法接受的。于是我们需要考虑如何优化并查集构造方式以减小树的深度,从而使得并查集的时间效率得以提高。
这里我们介绍一下并查集中最常见的两种优化:启发式(按秩)合并 及 路径压缩。

并查集优化 · 启发式(按秩)合并

这种优化方法的核心思路是,在合并两个并查集树的时候,将深度(或节点数)更小的一个并查集连到深度(或节点数)更大的一个上,从而降低合并并查集时造成的深度的增量。
所以我们需要一个辅助数组去记录每个并查集树的深度(或节点数)。这里分开两种写法吧。

  1. 深度式写法
    //假设dep[u]表示u子树(以u为根的并查集)的深度。初始值均为1.
    void merge(int u,int v){
    u = find(u);
    v = find(v);//分别寻找所在并查集的根
    if(dep[u] < dep[v])
        swap(u,v);//保证小的往大的上合并
    f[v] = u;
    if(dep[u] == dep[v])
        dep[u]++;//如果合并的两个树深度相等就要更新合并后的树的深度了
    return;
    }```
    </li>
    <li>子树节点数式写法
    ```cpp
    //假设siz[u]表示u的子树内(以u为根的并查集中)的节点个数,初始值均为1.
    void merge(int u,int v){
    u = find(u);
    v = find(v);//分别寻找所在并查集的根
    if(siz[u] < siz[v])
        swap(u,v);//保证小的往大的上合并
    f[v] = u;
    siz[u] += siz[v];//这里直接加上去就行了,因为是把树接上去了。
    return;
    }
    

    这种优化方式主要着眼于对merge函数进行优化。
    大概可以证明,这种优化方式的查询时O(logn)的,证明不给出(其实是不会证)。

    并查集优化 · 路径压缩

    这种方式的优化主要着眼于对find函数进行优化,在递归的时候调整并查集的深度,使并查集的深度始终保持在一个较小的值。
    如果我们的并查集只需要实现上述两个功能,不需要记录树的结构的话,我们就可以破坏原树的结构来降低并查集的深度。
    我们注意到并查集的主要的两个操作几乎只关注并查集的根,而对每个点的父节点并不怎么关注。所以我们大多数情况下没必要记录原树的结构,只需要记录住每个点在哪个并查集就可以了。这时我们的f[u]的含义就发生了一些变化,它不再是原父亲节点了,而是记录了与u同并查集的一个较浅层的u的祖先节点。
    我们在递归寻找u所在并查集的根节点时,就可以对f[u]进行更新,只要找到,我们就更新f[u]为当前并查集的根节点,对于u到根节点路径上的所有节点都同理。所以我们把这种方法叫做路径压缩。
    这种优化方式与原代码的区别为find函数:

    int find(int x){
    if(x != f[x])
        f[x] = find(f[x]);//路径压缩的核心,更新路径上点的f
    return f[x];//这里一定要写成f[x];
    }

    这种优化的时间效率极高,一次查询的时间复杂度大概为 反阿克曼函数,其取值在大多数情况下不超过常数4。

    并查集的经典应用————Kruskal算法

    在最小生成树的kruskal算法中,我们总是要寻找最小的边,并试图将其加入当前已经形成的伪生成树。在尝试的时候我们就需要判断当前边的两个顶点是否在同一连通块中,如果是那么我们就不能加当前这条边。
    如果我们暴力寻找的话,效率会十分低下,这时候我们就可以使用并查集来协助记录连通块。
    对于一条边, 先用find分别寻找u和v所在的并查集的根节点,如果相同就跳过该边,否则生成树中加入该边,并将两并查集合并(连通块合并了)。
    如此找出n-1条边,就完成了Kruskal算法。

    并查集的缺陷以及其延申

    实际上并查集可以记录一些其他信息,那种叫做带权并查集,这里不再展开描述。
    但是有一个很严重的问题,并查集没法进行删除操作,普通并查集也无法进行撤销操作。这是并查集本身结构决定的事情。
    并查集是无法进行删除操作的,但是通过改造,却可以实现撤销和历史回溯操作。
    讲到历史回溯,立马就想到了可持久化数据结构。
    没错,就是基于可持久化线段树结构的可持久化并查集。
    不过可持久化并查集不能使用路径压缩优化(这是可持久化的问题),只能使用启发式(按秩)合并的优化。像了解的同学建议学一下可持久化线段树,然后再来我的博客Icontofig’s Blog中找到对应文章学习。


某例题叙述

至于为什么不放题目,原因是因为我忘了那个题在哪了……(雾)
大概意思是这样的……
给出一张连通图,每个时刻会有一个边被破坏掉,问每个时刻这个连通图的连通块个数。
连通块个数啊,好办,用并查集就好了,看有多少个结点i满足f[i] = i就是多少个连通块了(根的个数)
但是这是删除边的操作啊,并查集不是不能删除吗?
对于这道题来说,毕竟只有删除操作,其余啥也没有,所以我们可以把过程倒过来,从最后一个时刻向前推移,边的删除就成为了倒序的边的加入。这样就成了连通块合并了!
每次合并只需要看一下当前要合并的两个并查集是否是一个并查集,如果不是,连通块个数-1,合并两并查集,否则连通块个数保持原值,并查集也并不需要合并。
我们只需要把最后时刻,即删除掉所有要删除的边后的图的所有并查集预处理出来,然后倒序去加边合并就可以了。

本期并查集的讲解就到这里吧……虽然有点摸鱼没有讲带权并查集。
本文作者 Icontofig’s Blog

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据