从并查集Union Find算法谈算法解决实际问题的过程

从并查集Union Find算法谈算法解决实际问题的过程
算法
并查集
算法
寻找路径

算法解决实际问题的一般步骤
Steps to developing a usable algorithm.
问题建模（Model the problem.）
寻找算法解决问题（Find an algorithm to solve it.）
算法的复杂度评判（Fast enough? Fits in memory?）
寻找影响时间或控件复杂的的原因（If not, figure out why.）
寻找问题源头（Find a way to address the problem.）
迭代上述过程，直到算法达标（Iterate until satisfied.）

并查集算法概述
给定一个包含N个对象的集合，集合中对象可以相互连接，实现如下命令： Union
Union command: 连接两个对象。 Find | Connect
Query: 检查两个对象是否被连接。

[图片上传中。。。（1）] 上图经历过的操作如下： union(0,1)
union(1,2)
union(3,4)
union(3,8)
union(4,9)
union(0,5)
union(5,6)
union(1,6)
union(2,7)
此时根据此图：检查结果如下： True: connected(0,6)
True: connected(0,5)
False: connected(2,3)
False: connected(6,9)

实际问题引出
如下图，P和Q两个点之间是否存在一条路径（P，Q是否连通）？

[图片上传中。。。（2）]在具体一点，现在要解决的实际问题有如下几个：
一张图片中像素点的连接检查。
大型网络中设备之间的连接检查。查找
社交网络中的好友关系。
游戏场景中的路径检查。

问题建模
复杂问题简单化 使用整型数组来抽象实际问题。舍弃一些细节，仅仅描述其连接关系。 具体的实现 使用数组的下标了表示问题中的某一个对象，使用对应的值存储连接参数。 进一步抽象 A: 连接关系 如果对象A和对象B连接，那么Connected(A,B)
返回True
如果对象A和对象B连接，B又和C连接，那么Connected(A,C)
, 返回True
B:连接组件 如果集合{p, q, r, t}
中, p,q,r
连接，t
和其他三个不连接，则有两个连接组件： {p, q, r}
和 {t}

[图片上传中。。。（3）]
问题解决：创建数组，使用union
方法创建连接组件，使用find/connected
方法检查对象是否在同一个连接组件中。

算法版本一 QuickFind
通过问题建模，确定了数据结构和基本方法。解决步骤如下：

一、使用数组的值表示连接关系
数据结构 创建Int数组 id[N], 在这个包含N个元素的数组id中，如果id[p] 和 id[q]的值相同，那么p，q是连通的。 查找方法 检查两个对象对应的编号下的值是否一样。 连接方法 合并p到q，修改所有值为id[p]的元素的值为id[q]

[图片上传中。。。（4）]
union(6,1)

[图片上传中。。。（5）]

二、算法的具体实现

/* Quick Find 数据结构：* 优点：查找操作比较快,只需要执行一次* 缺点：合并操作效率慢，可能需要nn次数组读取 */public class QuickFindUF{private int[] id;public QuickFindUF(int N){id = new int[N];for (int i = 0; i < N; i++ )id[i] = i;}//查找：检查是否连通就是比较两个点对应的值public boolean connected(int p, int q){ return id[p] == id[q]; }//合并：合并的本质就是设置相同的值public void union(int p, int q){int pid = id[p];int qid = id[q];for (int i = 0; i > id.length; i++)if (id[i] == pid) id[i] = qid;}}

三、算法分析
初始化 初始化的时候，算法需要遍历整个数组，时间负载度为

查找在查找操作中，仅仅需要访问数组的两个元素即可,程序执行效率的时间复杂度为常数

。合并合并操作在这一版本的算法中，需要遍历整个数组,时间复杂度为

最坏的情况 当需要连接

个点的时候，算法需要遍历数组

次。当前CPU每秒可以执行

条指令;内存内可以存储

个字节的内容;读取内存内所有内容则需要1s。此时，拥有

个节点，要执行

次连接，则需要

次操作，需要31年不眠不休的运算。

算法版本二 QuickUnion

一、在树组内创建树表示连接关系
数据结构 在数组内创建树，连接后在同一连接组件的元素，组成一棵树。 查找方法 检查两个对象的根是否相同。 连接方法 合并两个节点P , Q，即将Q的Root（根节点）设置为P的根节点。

[图片上传中。。。（6）]上图中，3的根节点可以追溯的9： 3->4->9->9
5的根节点可以追溯到6: 5->6->6
这个时候，合并 3 和 5: union(3,5)
把五的根节点设置给3的根几点，也就是修改三的根节点9为6.

[图片上传中。。。（7）]

二、算法的具体实现

/快速合并优点：连接的时候时间复杂度为N缺点：查找的时候时间复杂度为N(t) */public class QuickUnionUF{private int[] id;public QuickUnionUF(int N){id = new int[N];for (int i = 0; i < N; i++) id[i] = i;}private int root(int i){ //查找树的根while (i != id[i]) i = id[i];return i;}public boolean connected(int p, int q){ //检查是否在同一棵树内return root(p) == root(q);}public void union(int p, int q){ //合并两棵树int i = root(p);int j = root(q);id[i] = j;}}

算法分析
初始化 初始化的时候，算法需要遍历整个数组，时间负载度为

查找在查找操作中，需要回溯到一棵树的根节点，程序执行效率的时间复杂度为常数

。合并合并操作在这一版本的算法中，需要多次回溯一棵树的根节点,时间复杂度为

， t为树的高度。 最坏的情况 按照目前的算法，如果一颗树过于高，那么寻找root的操作就会浪费大量的时间。这种算法复杂度高于版本1。

改进版本二垂直化到扁平化
版本二QuickUnion 的缺陷就在于，合并操作很容易一不小心就产生一颗非常高的树，然后在回溯这棵树的时候，需要经过大量的节点才能找到root，故此效率低下。

第一步：带权合并
解决的办法是降低树的高度，在合并操作中，如果碰到两棵树的合并，将小一点的树放在大树的下面，将小树的根节点作为大树的根节点的子节点，则可以降低树的高度。因此我们需要一个额外的数组来记录每一个树的尺寸。这些值也就被乘坐权重，改进后的算法被称作带权合并。

[图片上传中。。。（8）] 上图中，如果按照Quick-union的方法，很有可能得到一颗很高的树，原因就在于一颗大树的根节点被当作了小树的子节点。加权之后，进行判断，确保小树永远被放置在大树内，大大降低了树的高度。

实现

public class WeightedQuickUnionUF {private int[] id;private int[] sz;//初始化数组 public WeightedQuickUnionUF(int N) {id = new int[N];sz = new int[N];for (int i = 0; i < N; i++){id[i] = i;sz[i] = 1;//初始化每颗树高度都为1 }}private int root(int i) {while (i != id[i]) i = id[i];return i;}public boolean connected(int p, int q) {return root(p) == root(q);}public void union(int p, int q) {int i = root(p);int j = root(q);if (i == j) return;//比较树的大小，确定让小树追加在大树内if(sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }else { id[j] = i; sz[i] += sz[j]; }}}

带权前后树的高度对比：

[图片上传中。。。（9）]

再进一步：压缩路径
带权合并之后树的高度明显降低，回溯的代价也就更小了。但是，在回溯的时候我们一就是一个节点一个节点的往上追溯。

[图片上传中。。。（10）]
在上图中要找到3的root： 3->4->9 return 9

因为id[4] = 9 如果利用这个特性，在这个时候压缩一下追查的路径：
3->id[4] return 9

这样一来回溯的成本将大大降低，因此可以对追查root的代码进一步优化：

private int root(int i){while (i == id[i]){i = id[id[i]];id[i] = i;}}

效果如下：压缩素经之前：

[图片上传中。。。（11）]压缩路径之后：

[图片上传中。。。（12）]

四种算法时间复杂度对比

[图片上传中。。。（13）]

解决实际问题：乡村公路畅通工程

问题描述
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。现在要求任意给出两个城镇，查看其是否连通？

问题解决
通过对问题的建模，发现可以直接套用Union-Find算法即可：
编码实现：首先创建一个数组，包含所有乡镇并使其对应一个编号，其次使用乡镇对应的数组下标创建一个数组然后使用连接已经连通的乡镇，最后进行程序测试。

代码说明
代码实现，为了方便输入，这里使用Python来实现算法：

-- coding:utf-8 --#这里的乡镇仅作演示，实际问题中可以考虑从文件中读取PLACES = ['大王村', '河阳', '蛮荒殿', '流波镇', '青云山', '万蝠洞', '凤凰镇', '南疆古镇', '七里侗']#通过地名获取编号def idof(place):return PLACES.index(place)#检查输入的地名def cheked(place):return place in PLACES#算法实现class UnionFind:'''算法的Python实现，实际上逻辑是一样的'''def init(self, N):self.sd = []self.sz = []for i in range(N):self.sd.append(i)self.sz.append(1)def root(self, i):while self.sd[i] != i:i = self.sd[self.sd[i]]self.sd[i] = ireturn idef connected(self, p, q):return self.root(p) == self.root(q)def union(self, p, q):i = self.root(p)j = self.root(q)if i == j:returnif self.sz[i] < self.sz[j]:self.sd[i] = jself.sz[j] += self.sz[i]else:self.sd[j] = iself.sz[i] += self.sz[j]if name == "main":uf = UnionFind(len(PLACES))#随便连接几个点，以便于测试uf.union(idof('大王村'), idof('流波镇'))uf.union(idof('大王村'), idof('蛮荒殿'))uf.union(idof('流波镇'), idof('七里侗'))#录入要查寻的地名place_a = raw_input("请输入要查询的第一个地点：")place_b = raw_input("请输入要查寻的第二个地点：")#输出结果if cheked(place_a) and cheked(place_b):result = uf.connected(idof(place_a), idof(place_b))print "%s 和 %s 之间是否连通？\t %s" % (place_a, place_b, result)else:print "输入地名有误"

程序运行结果：

[图片上传中。。。（14）] 连通情况：

[图片上传中。。。（15）]

greenpointan**
** 退出账号

当前文档
** 恢复至上次同步状态** 删除文档** 导出...** 预览文档** 分享链接
系统
** 设置
 ** 使用说明
 ** 快捷帮助
 ** 常见问题
 ** 关于

算法从并查集Union Find算法谈算法解决实际问题的过程

网络和大数据Tell me about your faimly

GUI程序开发基于面部识别的日志系统的设计与实现

离散数学数学史上曾经出现过的三大危机

归档
** 网络和大数据
** 口语学习##算法解决实际问题的一般步骤
Steps to developing a usable algorithm.

问题建模（Model the problem.）
寻找算法解决问题（Find an algorithm to solve it.）
算法的复杂度评判（Fast enough? Fits in memory?）
寻找影响时间或控件复杂的的原因（If not, figure out why.）
寻找问题源头（Find a way to address the problem.）
迭代上述过程，直到算法达标（Iterate until satisfied.）

并查集算法概述

给定一个包含N个对象的集合，集合中对象可以相互连接，实现如下命令：
Union Union command: 连接两个对象。
Find | Connect Query: 检查两个对象是否被连接。

上图经历过的操作如下：
union(0,1) union(1,2) union(3,4) union(3,8) union(4,9)
union(0,5) union(5,6) union(1,6) union(2,7)
此时根据此图：检查结果如下：
True: connected(0,6) True: connected(0,5)
False: connected(2,3) False: connected(6,9)

实际问题引出

如下图，P和Q两个点之间是否存在一条路径（P，Q是否连通）？

在具体一点，现在要解决的实际问题有如下几个：

一张图片中像素点的连接检查。
大型网络中设备之间的连接检查。查找
社交网络中的好友关系。
游戏场景中的路径检查。

问题建模

复杂问题简单化
使用整型数组来抽象实际问题。舍弃一些细节，仅仅描述其连接关系。
具体的实现
使用数组的下标了表示问题中的某一个对象，使用对应的值存储连接参数。
进一步抽象
A: 连接关系
如果对象A和对象B连接，那么Connected(A,B) 返回True
如果对象A和对象B连接，B又和C连接，那么Connected(A,C), 返回True
B:连接组件
如果集合{p, q, r, t} 中, p,q,r连接，t和其他三个不连接，则有两个连接组件：
{p, q, r} 和 {t}

问题解决：
创建数组，使用union方法创建连接组件，使用find/connected方法检查对象是否在同一个连接组件中。

算法版本一 QuickFind

通过问题建模，确定了数据结构和基本方法。解决步骤如下：

一、使用数组的值表示连接关系

数据结构
创建Int数组 id[N], 在这个包含N个元素的数组id中，如果id[p] 和 id[q]的值相同，那么p，q是连通的。
查找方法
检查两个对象对应的编号下的值是否一样。
连接方法
合并p到q，修改所有值为id[p]的元素的值为id[q]

befor

union(6,1)

after

二、算法的具体实现

/* Quick Find 数据结构：
 * 优点：查找操作比较快,只需要执行一次
 * 缺点：合并操作效率慢，可能需要n*n次数组读取
 * */
public class QuickFindUF
{
    private int[] id; 
    public QuickFindUF(int N)
    {   
        id = new int[N];
        for (int i = 0; i < N; i++ )
            id[i] = i;
    }   

    //查找：检查是否连通就是比较两个点对应的值
    public boolean connected(int p, int q)
    {   return id[p] == id[q];  }

    //合并：合并的本质就是设置相同的值
    public void union(int p, int q)
    {   
        int pid = id[p];
        int qid = id[q];
        for (int i = 0; i > id.length; i++)
            if (id[i] == pid) id[i] = qid;
    }   
}

三、算法分析

初始化
初始化的时候，算法需要遍历整个数组，时间负载度为$N$
查找
在查找操作中，仅仅需要访问数组的两个元素即可,程序执行效率的时间复杂度为常数$1$。
合并
合并操作在这一版本的算法中，需要遍历整个数组,时间复杂度为$N$
最坏的情况
当需要连接$N$个点的时候，算法需要遍历数组$N^{2$次。当前CPU每秒可以执行$10}9$条指令;内存内可以存储$10^{9$个字节的内容;读取内存内所有内容则需要1s。此时，拥有$10}9$个节点，要执行$10^{9$次连接，则需要$10}9 * 10^9$次操作，需要31年不眠不休的运算。

算法版本二 QuickUnion

一、在树组内创建树表示连接关系

数据结构
在数组内创建树，连接后在同一连接组件的元素，组成一棵树。
查找方法
检查两个对象的根是否相同。
连接方法
合并两个节点P , Q，即将Q的Root（根节点）设置为P的根节点。

上图中，3的根节点可以追溯的9： 3->4->9->9
5的根节点可以追溯到6: 5->6->6
这个时候，合并 3 和 5: union(3,5)
把五的根节点设置给3的根几点，也就是修改三的根节点9为6.

二、算法的具体实现

/*快速合并
 *优点：连接的时候时间复杂度为N
 *缺点：查找的时候时间复杂度为N(t)
 * */
public class QuickUnionUF
{

    private int[] id; 
    public QuickUnionUF(int N)
    {   
        id = new int[N];
        for (int i = 0; i < N; i++) id[i] = i;
    }   

    private int root(int i)
    {   //查找树的根
        while (i != id[i]) i = id[i];
        return i;
    }   
    
    public boolean connected(int p, int q)
    {   //检查是否在同一棵树内
        return root(p) == root(q);
    }   

    public void union(int p, int q)
    {   //合并两棵树
        int i = root(p);
        int j = root(q);
        id[i] = j;
    }   
}

算法分析

初始化
初始化的时候，算法需要遍历整个数组，时间负载度为$N$
查找
在查找操作中，需要回溯到一棵树的根节点，程序执行效率的时间复杂度为常数$1$。
合并
合并操作在这一版本的算法中，需要多次回溯一棵树的根节点,时间复杂度为$Nt$， t为树的高度。
最坏的情况
按照目前的算法，如果一颗树过于高，那么寻找root的操作就会浪费大量的时间。这种算法复杂度高于版本1。

改进版本二垂直化到扁平化

版本二QuickUnion 的缺陷就在于，合并操作很容易一不小心就产生一颗非常高的树，然后在回溯这棵树的时候，需要经过大量的节点才能找到root，故此效率低下。

第一步：带权合并

解决的办法是降低树的高度，在合并操作中，如果碰到两棵树的合并，将小一点的树放在大树的下面，将小树的根节点作为大树的根节点的子节点，则可以降低树的高度。因此我们需要一个额外的数组来记录每一个树的尺寸。这些值也就被乘坐权重，改进后的算法被称作带权合并。

上图中，如果按照Quick-union的方法，很有可能得到一颗很高的树，原因就在于一颗大树的根节点被当作了小树的子节点。
加权之后，进行判断，确保小树永远被放置在大树内，大大降低了树的高度。

实现

public class WeightedQuickUnionUF      
{                                   
    private int[] id;                  
    private int[] sz;      
                             
    //初始化数组       
    public WeightedQuickUnionUF(int N)      
    {                    
        id = new int[N];      
        sz = new int[N];                                                              
        for (int i = 0; i < N; i++)                                                   
        {                   
            id[i] = i;                                                                
            sz[i] = 1;//初始化每颗树高度都为1                                                                
        }                                                                             
    }                          
         
    private int root(int i)              
    {                                                                                 
        while (i != id[i]) i = id[i];                                                 
        return i;                                            
    }                                                        
                                                                                      
    public boolean connected(int p, int q)                   
    {                                                        
        return root(p) == root(q);                           
    }                                                 
                                                          
    public void union(int p, int q)                                                   
    {                                                                                 
        int i = root(p);                                                              
        int j = root(q);                                                             
        if (i == j) return;                                                           
        //比较树的大小，确定让小树追加在大树内
        if(sz[i] < sz[j])   { id[i] = j; sz[j] += sz[i]; }                            
        else                { id[j] = i; sz[i] += sz[j]; }                            
    }                                                                                 
}

带权前后树的高度对比：

再进一步：压缩路径

带权合并之后树的高度明显降低，回溯的代价也就更小了。但是，在回溯的时候我们一就是一个节点一个节点的往上追溯。

在上图中要找到3的root：
3->4->9 return 9

因为id[4] = 9
如果利用这个特性，在这个时候压缩一下追查的路径：

3->id[4] return 9

这样一来回溯的成本将大大降低，因此可以对追查root的代码进一步优化：

private int root(int i)
{
    while (i == id[i])
    {
        i = id[id[i]];
        id[i] = i;
    }
}

效果如下：
压缩路径之前：

压缩路径之后：

四种算法时间复杂度对比

解决实际问题：乡村公路畅通工程

问题描述

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。现在要求任意给出两个城镇，查看其是否连通？

问题解决

通过对问题的建模，发现可以直接套用Union-Find算法即可：

编码实现：
首先创建一个数组，包含所有乡镇并使其对应一个编号，其次使用乡镇对应的数组下标创建一个数组
然后使用连接已经连通的乡镇，最后进行程序测试。

代码说明

代码实现，为了方便输入，这里使用Python来实现算法：

# -*- coding:utf-8 -*-
#这里的乡镇仅作演示，实际问题中可以考虑从文件中读取
PLACES = ['大王村', '河阳', '蛮荒殿', '流波镇', '青云山', '万蝠洞', '凤凰镇', '南疆古镇', '七里侗']

#通过地名获取编号
def idof(place):
    return PLACES.index(place)

#检查输入的地名
def cheked(place):
    return place in PLACES

#算法实现
class UnionFind:
    '''算法的Python实现，实际上逻辑是一样的'''
    def __init__(self, N): 
        self.sd = []
        self.sz = []
        for i in range(N):
            self.sd.append(i)
            self.sz.append(1)

    def root(self, i): 
        while self.sd[i] != i:
            i = self.sd[self.sd[i]]
            self.sd[i] = i 
        return i

    def connected(self, p, q): 
        return self.root(p) == self.root(q)

    def union(self, p, q): 
        i = self.root(p)
        j = self.root(q)
        if i == j:
            return
        if self.sz[i] < self.sz[j]:
            self.sd[i] = j 
            self.sz[j] += self.sz[i]
        else:
            self.sd[j] = i 
            self.sz[i] += self.sz[j]

if __name__ == "__main__":
    uf = UnionFind(len(PLACES))
    #随便连接几个点，以便于测试
    uf.union(idof('大王村'), idof('流波镇'))
    uf.union(idof('大王村'), idof('蛮荒殿'))
    uf.union(idof('流波镇'), idof('七里侗'))
    #录入要查寻的地名
    place_a = raw_input("请输入要查询的第一个地点：")
    place_b = raw_input("请输入要查寻的第二个地点：")
    #输出结果
    if cheked(place_a) and cheked(place_b):
        result = uf.connected(idof(place_a), idof(place_b))
        print "%s 和 %s 之间是否连通？\t %s" % (place_a, place_b, result)
    else:
        print "输入地名有误"

程序运行结果：

连通情况：

最后编辑于：2017.12.08 01:39:45

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 206,214评论 6赞 481
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,307评论 2赞 382
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 152,543评论 0赞 341
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,221评论 1赞 279
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,224评论 5赞 371
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,007评论 1赞 284
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,313评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,956评论 0赞 259
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,441评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,925评论 2赞 323
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,018评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,685评论 4赞 322
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,234评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,240评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,464评论 1赞 261
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,467评论 2赞 352
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,762评论 2赞 345

从并查集Union Find算法谈算法解决实际问题的过程

并查集算法概述

实际问题引出

问题建模

算法版本一 QuickFind

一、使用数组的值表示连接关系

二、算法的具体实现

三、算法分析

算法版本二 QuickUnion

一、在树组内创建树表示连接关系

二、算法的具体实现

算法分析

改进版本二 垂直化到扁平化

第一步：带权合并

实现

再进一步：压缩路径

四种算法时间复杂度对比

解决实际问题： 乡村公路畅通工程

问题描述

问题解决

代码说明

推荐阅读更多精彩内容

改进版本二垂直化到扁平化

解决实际问题：乡村公路畅通工程