算法"/>
03.并查集和克努斯卡尔最小生成树算法
相关代码地址:
一、并查集是什么
英文union find,有人说并查集是最简洁而优雅的数据结构之一,主要用于解决一些元素分组的问题。它管理一系列不相交的集合,并支持两种操作:
-
合并(Union):把两个不相交的集合合并为一个集合。
-
查询(Find):查询两个元素是否在同一个集合中。
形象的解释一下,并查集的使用过程:
就好像是一个盘子里有很多小水滴,你给他们编好号,如:1、2、3、4、5 ... ... 。
合并:就好像是,把这些小水滴,用筷子拨到一起(可以是两个单独的水滴;也可以是,1个单独的水滴和已经合并过的大水滴;也可以是两个和并过的大水滴)。
查询:比如查询 1号和5号是不是再一个大水滴里(可以是1和5之前合并成了一个有两滴水的水滴;也可以是,2、3、4组成的大水滴,和 5、6组成的大水滴合并成了有5个元素的水滴)。
二、并查集的使用场景
-
克努斯卡尔(Kruskal)最小生成树算法。
-
网格渗透Grid percolation
-
网格中有一堆原点,检查是否存在路径,从底部的点到达顶部的点
-
-
网络连接问题
-
检查图中的两个点,是否有边把他们连接起来。
-
-
树中的最近公共祖先
-
图像处理
三、并查集的时间复杂度
构建 | O(n) |
---|---|
合并(Union) | O(1) |
查找(Find) | O(1) |
获取某个组的大小 | O(1) |
检查组是否连接 | O(1) |
检查组的数量 | O(1) |
四、图形演示
1. 查找和合并
查找:为了查找某个元素属于哪个组,只要不断查找该元素的父节点,一直到根结点为止(根结点指向自己)
合并:为了将两元素合并,只要找到这两个元素的根节点,如果他们的根节点不相同,就将其中一个根结点指向另外一个根结点。通常将元素较少的组,合并入元素较多的组。
(1) 初始时,元素自己一组,父元素都指向自己。
注意:根结点也是指向自己的,可以用这个来判断是否是跟节点。
(2) union(C,K)
合并时一般小的组,指向大的组,一样的随便选一个。
3. 路径压缩(优化操作复杂度)
上图是假象的,并查集合并的糟糕情况,这时要合并 E和L,就需要不停地向上寻找,一直找到 E的根结点(组)A和L的根结点(组)G。然后直接把 A指向G
这时候,如果做路径压缩的话,就是先把路径上的元素都指向根结点
然后在把A指向G
这样在查询某个元素时,把,自己和自己所有的祖先结点,全部指向根结点的操作,叫路径压缩
路径压缩,可以减少查找父元素的次数,优化查询。
对于并查集数据结构,我们通常不做 分开 un-union 操作
组的数量定义根结点的数量。并且,组的数量只会减少,不会增加。
五、并查集的实现
package dataStructures type UnionFind struct {size intgroupSize map[string]intid map[string]stringnumGroups int } func (u *UnionFind) Init(elems []string) {u.size = len(elems)u.groupSize = make(map[string]int, u.size)u.id = make(map[string]string, u.size)u.numGroups = len(elems)for _, v := range elems {if v == "" {panic("ele can not be empty string")}u.groupSize[v] = 1u.id[v] = v} } func NewUnionFind(elems []string) *UnionFind {var u UnionFindu.Init(elems)return &u } func (u *UnionFind) Find(ele string) string {var num intvar root stringp := elefor {root = u.id[p]if root == p {break}p = rootnum++if num > u.size {panic("data error")}}//路径压缩p = elefor {next := u.id[p]if root != next {u.id[p] = root} else {break}p = next} return root } func (u *UnionFind) IsConnected(A, B string) bool {rootA := u.Find(A)rootB := u.Find(B)return rootA == rootB } func (u *UnionFind) Size() int {return u.size } func (u *UnionFind) Groups() int {return u.numGroups } func (u *UnionFind) GroupSize(ele string) int {root := u.Find(ele)return u.groupSize[root] } func (u *UnionFind) Unify(A, B string) {if _,ok := u.id[A];!ok {return}if _,ok := u.id[B];!ok {return}if u.IsConnected(A, B) {return}rootA := u.Find(A)rootB := u.Find(B)if u.groupSize[rootA] < u.groupSize[rootB] {u.groupSize[rootB] = u.groupSize[rootA] + u.groupSize[rootB]u.groupSize[rootA] = 0u.id[rootA] = rootB} else {u.groupSize[rootA] = u.groupSize[rootA] + u.groupSize[rootB]u.groupSize[rootB] = 0u.id[rootB] = rootA}u.numGroups -- }
六、图
1.基本概念
图:有穷集合V和边E的集合。集合中的点称为顶点(树中为节点)。
有向图和无向图:有向图--边有方向;无向图--边没有方向。
弧:有向图中的边称为弧;含箭头的顶点称为弧头,另外一边称为弧尾。
顶点的度、入度和出度:与顶点相连边的总数称为度, 有向图中,以顶点为弧头的边的总数称为 入度。 有向图中,以顶点为弧尾的边的总数称为 出度
有向完全图和无向完全图: 无向图中,n(n-1) /2 条边就可以把所有顶点全部直接连通,有n(n-1) /2 条边的无向图,称为无向完全图; 有向图中,n(n-1) 条弧,就可以把所有顶点都双向直接连通,有n(n-1) 条弧的有向图,称为有向完全图
路径和路径长度: 相邻边构成的序列,称为路径。路径上边的数目称为路径长度。
简单路径:路径中没有重复顶点称为,简单路径。
回路:起点和终端一样的路径
连通、连通图和连通分量:两个顶点直接有路径,称为连通;任意两顶点都连通称为连通图。极大连通子图,称为图的连通分量。
强连通图和强连通分量:有向图中,任意两个顶点都相互连通(A到B 、B到A都连通),强连通图
权和网:路径上有个对应数称为权,带权图,称为网。
2、图的存储结构
(1)邻接矩阵
(2)邻接表
(3)邻接多重表
七、克努斯卡尔-最小生成树算法
给出一个图G = (V,E),V表示顶点,E表示边,E上可以带有权重weight,我们需要在图中找出一颗最小生成树(可能并不唯一)。一棵最小生成树是图中所有边的一个子集,但是不能形成环,并且这些边上的权重总和是最小的。
运行克努斯卡尔算法后:
有可能有其他,最小生成树,总权重也是14.
1. 算法描述
-
根据边的权重,对边从小到大金星排序
-
对排序的边进行遍历,检查每一条边的两个顶点,如果这两个顶点已经合并过了(属于同一个组),那么我们就排除这条边(否则最小生成树中会形成环),否则我们就将这条边添加到最小生成树中,并将两对应顶点所在的组合合并成一个组。
-
当所有的边都被处理过,或者所有的顶点都已经被合并到一个大组,那么算法结束。
2.图形描述
(1)所有的边根据权重排序,根据权重大小依次处理每一条边。
(2)处理边I to J
(3)处理 A to E,CtoI
(4) E to F ,GH,DB,
(5) c to j由于 C和j已经在一个组里,抛弃C,J
如何知道,cj再一个组呢?可以用并查集的find操作
(6)多次合并后,所有元素已经都在一个组里,放弃剩下的边。
本文,参考了波波老师,数据结构视频中并查集的部分。
更多推荐
03.并查集和克努斯卡尔最小生成树算法
发布评论