· 并查集解决什么问题

如果给你一个图里面有一些顶点，并且告诉你图中每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数组辅助，效率还是略微高一些，比如下面这种情况：

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

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