更多优质内容
请关注公众号

算法小白的入门日记(二一)图的连通性问题——Union-Find 并查集-张柏沛IT博客

正文内容

算法小白的入门日记(二一)图的连通性问题——Union-Find 并查集

栏目:算法专题 系列:算法小白的入门日记 发布时间:2022-01-23 14:23 浏览量:217
本系列文章目录
展开/收起

· 并查集解决什么问题

如果给你一个图里面有一些顶点,并且告诉你图中每2个顶点的连接关系,你如何才能快速的找出任意给出的两个顶点是否具有连通性呢?

例如:下面的图结构给出了顶点与顶点之间的连接关系,那么,我们如何快速知道 (0, 3) , (1, 5), (7, 8) 是否相连呢?

 

并查集就可以解决这样的问题:用来快速判断网络中两个节点的连通性。

而且和最小生成树的连通性不同,并查集侧重动态连通性,即两个节点可以发生union连接操作,而最小生成树的所有节点是本身已经连接好了的。

 

·并查集算法和 数据结构

并查集在逻辑上是一个用森林(若干棵 互相独立的树 )表示的图,在物理上使用一个一维数组parent表示这片森林( 的所有树),parent[i]表示节点i的父节点。     

  如上图所示,整个图结构包含4棵 独立的树。   

 

算法主要需要实现这两个 API: 

class UF {
    /* 将 p 和 q 连接 */
    public void union(int p, int q);

    /* 判断 p 和 q 是否连通 */
    public boolean connected(int p, int q);

    /* 返回图中有多少个连通分量,即多少棵独立的树 */
    public int count();
}

 

 

并查集有2种实现方式:

Quick Find 实现方式:指的是实现「并查集」时,findRoot 函数时间复杂度为 O(1),union 函数的时间复杂度为 O(N)。
Quick Union 实现方式:指的是实现「并查集」时,findRoot 函数时间复杂度为 O(logN),union 函数的时间复杂度也为 O(logN)。

 

- Quick Union 实现方式

1、初始化init

初始化UF时,需要指定节点个数。初始状态下的每一个节点就是一棵树,节点的父节点就是自己,所有节点都不连通。

type UF struct{
   Parent []int   // 一维数组存储并查集的所有树(森林)
   Count int     // 记录连通分量
}

func (uf *UF) Init(n int){ // n是图的节点个数
   uf.Parent = make([]int, n)
   for i:=0; i<n; i++{
      uf.Parent[i] = i
   }
   uf.Count = n
}

 

 

2、连通两个节点connect

连通某两个节点 p 和 q ,其本质是将 p节点所在树的根节点P 与 q节点所在树的根节点Q 连通,即P的指针指向Q(Q作为父节点)或者Q的指针指向P(P为父节点)。谁做父节点都一样,根据连通的传递性,连通p和q后,P与Q这两棵树的所有节点都会连通,都能互相到达。

// 连接 p 和 q 两个节点
func (uf *UF) Union(p int, q int){
   P := uf.findRoot(p)
   Q := uf.findRoot(q)
   if P == Q{	// 说明 p 和 q已经在同一棵树下,已经连通
       return   
   }
   uf.count--
   uf.Parent[P] = Q   // Q作为父节点
}

// 寻找某节点的父节点
func (uf *UF) findRoot(node int) int{
   for uf.Parent[node] != node{   // 当遍历到某个节点的父节点是自己时,该节点就是node所在的树的根节点
      node = uf.Parent[node]
   }
   
   return node
}

 

3、判断两个节点是否连通

只要两个节点在同一棵树上(判断p和q根节点是否为同一个根节点),他们就是相连的。

// 判断p和q是否连通
func (uf *UF) Connected(p, q int) bool{
   return uf.findRoot(p) == uf.findRoot(q)
}

 

Quick Union 实现方式下的Union()和Connected()的性能都取决于findRoot的性能,findRoot的平均时间复杂度为O(logn),即树高。

 

 

- Quick Find实现方式

Quick Find为了实现 findRoot 为O(1)的复杂度,需要保持森林中的每棵树最多保持2层的高度。因此连通p和q这2个节点时,需要将p节点所在的树上所有节点打散后,添加到q所在树下。

// 连接 p 和 q 两个节点
func (uf *UF) Union(p int, q int){
	P := uf.findRoot(p)
	Q := uf.findRoot(q)
	if P == Q{	// 说明 p 和 q已经在同一棵树下,已经连通
		return
	}

	// 将p所在的树的所有节点都打散添加到q所在的树(的根节点)下
	for i:=0; i<len(uf.Parent);i++{
		if uf.findRoot(i) == P{	// 如果某个节点在P树下,让其改投到Q树下
			uf.Parent[i] = Q
		}
	}
	uf.Count--
}

// 寻找某节点的父节点
func (uf *UF) findRoot(node int) int{
	return uf.Parent[node]
}

Quick Find 实现方式下的Connected()的性能取决于findRoot的性能,即O(1),Union()性能为O(n)。

 

 

· 平衡性优化——按秩合并

Quick Union 实现方式下,除了初始化Parent数组需要O(n)复杂度之外,UF算法的性能取决于findRoot的性能。findRoot要做的是从某一个子节点顺着向上指针找到父节点,因此复杂度是树的高度,即O(logn)。然而这不是一定的,如果恰好每次调用 Union 都把一个大树的父指针指向一棵小树的根节点,那么树的高度会不断增大,最坏会退化为一个链表,此时findRoot的复杂度最坏退化为O(n)。

 

为了findRoot稳定维持在O(logn),需要想办法每次Union()完之后,树依旧保持平衡(树的所有分支的高度差近似相等)。

具体做法是Union时让小树的根节点P指向大树的根节点Q,不要让大树指向小树,这样树的高度就不会增加。

 

假如大树P的最大高度为10,小树Q最大高度为5:

小树P -> 大树Q, 最大高度还是10

大树Q -> 小树P,最大高度变成11

 

为此我们需要一个Size数组记录每个树的节点个数,并且优化Union():

// 连接 p 和 q 两个节点
func (uf *UF) Union(p, q int){
   P := uf.findRoot(p)
   Q := uf.findRoot(q)
   if P == Q{ // 说明 p 和 q已经在同一棵树下,已经连通
      return
   }

   if uf.Size[P] > uf.Size[Q]{    // P是大树
      uf.Parent[Q] = P   // P作为父节点
      uf.Size[P] += uf.Size[Q]  // Size数组记录每个树的节点个数
   }else{
      uf.Parent[P] = Q   // Q作为父节点
      uf.Size[Q] += uf.Size[P]
   }
   uf.count--
}

size大的树就是大树,这样树的高度和findRoot的复杂度就维持在O(log(n))。

 

我还见过其他方法是用size数组存储每个节点的高度,而不是树的节点个数,初始高度为1。

// 连接 p 和 q 两个节点
func (uf *UF) Union(p int, q int){
	P := uf.findRoot(p)
	Q := uf.findRoot(q)
	if P == Q{	// 说明 p 和 q已经在同一棵树下,已经连通
		return
	}

	if uf.Size[P] > uf.Size[Q]{
		uf.Parent[Q] = P
	}else if uf.Size[P] < uf.Size[Q]{
		uf.Parent[P] = Q
	}else{
		uf.Parent[Q] = P
		uf.Size[P] += 1
	}
}

 

所谓的按秩合并指按小树根节点指向大树根节点的秩序合并两棵树,“秩”具体是指树的高度或者树的节点数。按秩合并的并查集,其findRoot方法的复杂度可以稳定在O(logn)。

 

· 路径压缩

路径压缩是指进一步缩短树的高度,使每棵树从高瘦变成胖矮(增加根节点的分支数,即广度;减少树的高度),从而使得树的高度一直维持在常数级别(具体来说,是维持在3层以内),这样findRoot()的复杂度就会降至O(1),Connected和Union方法也会降到O(1)。

 

做法有2种:

1、执行findRoot时把遍历到的节点的向上指针从父节点指向祖父节点,相当于把遍历到的每个节点往上提,每个树最多只有3层。

func (uf *UF) findRoot(node int) int{
   for uf.Parent[node] != node{   // 当遍历到某个节点的父节点是自己时,该节点就是node所在的树的根节点
      uf.Parent[node] = uf.Parent[uf.Parent[node]]   // node的向上指针指向其祖父节点,7指向9,9再指向5
      node = uf.Parent[node]    // 从7找起,则会略过4和2
   }

   return node
}

 

2、执行findRoot时把遍历到的节点的向上指针全部指向根节点(使用后序遍历),每个树最多只有2层。

func (uf *UF) findRoot(node int) int{
	if uf.Parent[node] == node{
		return node
	}

	root := uf.findRoot(uf.Parent[node])
	uf.Parent[node] = root
	return root
}

 

 

· Union-Find算法完整版

type UF struct{
   Parent []int   // 一维数组存储并查集的所有树(森林)
   Size []int    // 每个节点作为根节点的树下的节点总个数
   count int     // 记录连通分量
}

func (uf *UF) Init(n int){ // n是图的节点个数
   uf.Parent = make([]int, n)
   uf.Size = make([]int, n)
   for i:=0; i<n; i++{
      uf.Parent[i] = i
      uf.Size[i] = 1
   }
   uf.count = n
}

// 连接 p 和 q 两个节点
func (uf *UF) Union(p, q int){
   P := uf.findRoot(p)
   Q := uf.findRoot(q)
   if P == Q{ // 说明 p 和 q已经在同一棵树下,已经连通
      return
   }

   if uf.Size[P] > uf.Size[Q]{    // P是大树
      uf.Parent[Q] = P   // P作为父节点
      uf.Size[P] += uf.Size[Q]
   }else{
      uf.Parent[P] = Q   // Q作为父节点
      uf.Size[Q] += uf.Size[P]
   }
   uf.count--
}

// 寻找某节点的父节点
func (uf *UF) findRoot(node int) int{
   for uf.Parent[node] != node{   // 当遍历到某个节点的父节点是自己时,该节点就是node所在的树的根节点
      uf.Parent[node] = uf.Parent[uf.Parent[node]]   // node的向上节点指向其祖父节点
      node = uf.Parent[node]
   }

   return node
}

// 判断p和q是否连通
func (uf *UF) Connected(p, q int) bool{
   return uf.findRoot(p) == uf.findRoot(q)
}

func (uf *UF) Count() int{
   return uf.count
}

 

既然有了路径压缩,size数组的按秩平衡还需要吗?这个问题很有意思,因为路径压缩保证了树高为常数(不超过 3),那么树就算不平衡,高度也是常数,基本没什么影响。

作者认为,论时间复杂度的话,确实,不按秩平衡也是 O(1)。但是如果加上size数组辅助,效率还是略微高一些,比如下面这种情况:

如果按秩平衡优化,一定会得到情况一,而不按秩平衡,可能出现情况二。情况一根本不会触发路径压缩,而情况二会多执行很多次路径压缩,将第三层节点压缩到第二层。

也就是说按秩平衡可以避免多余的路径压缩发生。




更多内容请关注微信公众号
zbpblog微信公众号

如果您需要转载,可以点击下方按钮可以进行复制粘贴;本站博客文章为原创,请转载时注明以下信息

张柏沛IT技术博客 > 算法小白的入门日记(二一)图的连通性问题——Union-Find 并查集

热门推荐
推荐新闻