2025年union-find算法

大家好，我是讯享网，很高兴认识大家。

查询图的连通分量

首先，前期准备。
我们假设输入 4 3 表示结点（4）与结点（3）相连，以此类推，输入5 4 表示结点（5）与结点（4）相连。
现在我们设置一个命名为id【】的数组，id初始化为下标的值。
id数组的意义如下，假如id[4]==id[3],那么便表示结点（4）与结点（3）相连，反之不相连，也就是不在同一个连通分量中。
那么我们想想，如果输入两个数i与j，通过判断id[i]与id[j]是否相等，是不是就能判断他们是在同一个连通分量中呢？答案是可以的。
那么应该如何实现。
首先明确id初始化的情况为:id[0] = 0,id[1] = 1,id[2] = 2…
可以理解为刚开始结点都是不连通的，故都不相等。
接下来通过输入边来进行连通。

quick-find算法

 public int find(int p) { 
    return id[p]; } public void union(int p,int q) { 
    int pid = find(p); int qid = find(q); if(pid==qid) return;//相等表示在同一个连通分量中，忽略。 //如果不相等，我们将数组中所有id[p]变为id[q]; for(int i=0;i<id.length;i++) { 
    if(id[i]==pid) id[i] = qid; } count--; }

讯享网

上面代码容易理解，但是我们容易发现时间复杂度很好，find操作很容易，但union操作每次都要扫描一遍数组，故时间是平方级别的。
接下来的优化方法是通过优化union操作进行的。
此时，id【】数组的含义变化了，它表示链接的下一个结点。
比如：id【4】 = 3表示4链接着3，id【3】 = 3表示3就是根节点了。
也就是说，我们用id【】数组用父链接的方式表示了一棵树。
那么此时，我们只要判断两个输入的根节点是否相同，就能判断他们是否在同一个连通分量中。

quick-union算法

讯享网

讯享网 //id[i] = x,表示i链接的下个结点为x public int find(int p) { 
    while(p!=id[p]) p = id[p]; return p; } public void union(int p,int q) { 
    int proot = find(p); int qroot = find(q); if(proot==qroot) return;//相等表示在同一个连通分量中，忽略。 //如果不相等，我们id[proot]变为qroot,也就是p的根节点设置为q id[prrot] = qroot; count--; } }

上面的算法，如果在最坏情况下，也就是构造出来的树是一条边，所耗费的时间也是巨大的，此时的优化方法便是，保证每次让小的树加到大的树上面，这里就需要一个数组sz【】来记录树的大小。

加权quick-union算法

//id[i] = x,表示i链接的下个结点为x public int find(int p) { 
    while(p!=id[p]) p = id[p]; return p; } public void union(int p,int q) { 
    int proot = find(p); int qroot = find(q); if(proot==qroot) return;//相等表示在同一个连通分量中，忽略。 //如果不相等，我们id[proot]变为qroot,也就是p的根节点设置为q if(sz[proot]<sz[qroot]) { 
    id[proot] = qroot;//将小树链接到大树上。 sz[qroot] += sz[proot];//大树的高度增加 }else { 
    id[qroot] = proot; sz[proot] += sz[qroot]; } count--; }

路径压缩加权quick-union算法

讯享网 //id[i] = x,表示i链接的下个结点为x public int find(int p) { 
    int t = p; while(p!=id[p]) p = id[p]; //将遍历过的结点都指向根节点 while(t!=id[p]) { 
    int temp = id[t]; id[t] = p;//都指向根节点 t = temp; } return p; } public void union(int p,int q) { 
    int proot = find(p); int qroot = find(q); if(proot==qroot) return;//相等表示在同一个连通分量中，忽略。 //如果不相等，我们id[proot]变为qroot,也就是p的根节点设置为q if(sz[proot]<sz[qroot]) { 
    id[proot] = qroot;//将小树链接到大树上。 sz[qroot] += sz[proot];//大树的高度增加 }else { 
    id[qroot] = proot; sz[proot] += sz[qroot]; } count--; }

查询图的连通分量

相关推荐