数据结构与算法（十）图的连通性问题——Union-Find 并查集 和 最小生成树算法

[ 程序员阿沛 ](javascript:void(0);)

01 并查集算法

并查集解决什么问题

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

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

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

并查集算法 和 数据结构

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

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

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

class UF {    /* 将 p 和 q 连接 */    public function union(int p, int q);
    /* 判断 p 和 q 是否连通 */    public function connected(int p, int q);
    /* 返回图中有多少个连通分量，即多少棵独立的树 */    public function 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数组辅助，效率还是略微高一些，比如下面这种情况：

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

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

02

最小生成树算法

最小生成树算法的作用是将一个图的多余边去除，使得图中所有顶点满足连通性的同时，边的数量减小到最小边数，或者说使边的权重总和最小，此时这个取出多余边的图我们称为最小连通子图，最小连通子图没有回路，因此是一个树形结构，又称为最小生成树。

最小生成树的应用场景很多，小到我们要来个欧洲十国游，怎么规划路径让交通费用最低，大到国家的电力网、公路网、通信网，怎么规划路径可以让建设成本最低，学习了最小生成树后，你就可以通过算法来计算出最佳路径了，不仅如此，所有涉及连接网络中所有节点的最优路径问题，都可以通过最小生成树来处理。

如果我们将每条边看成是一个顶点到达另一个顶点的成本，最小生成树算法的目的是将整个图所有节点连通的成本最小化。而最短路径算法则是算出任意两个节点连通的最小成本。

例如一个图原本的样子是这样

变成最小生成树后是这样

最小生成树算法采用贪心算法：

1、创建一个“已连通集合（已触达顶点集合）”用于存放已经遍历过并且加入到生成树的顶点。创建一个一维数组arr表示最小生成树，顶点 i 的父节点为
arr[i]。生成树arr有一个虚拟根节点 -1。

2、从图中任意选择一个顶点A加入到“已连通集合”，节点A作为 arr 的下标0，arr[0] = -1，即顶点A的父节点是虚拟节点 -1。

3、从“已连通集合”中选择一个from节点，要求from节点和from的未访问过的相邻节点to节点的距离最小。将to顶点加入到“已连通集合”和最小生成树中。

4、重复上述过程，直到原图的所有顶点都加入到“已连通集合”和最小生成树中。

所生成的最小生成树的边的条数 = 总顶点数 - 1 = n - 1

代码实现如下：

// 最小生成树算法func buildMinTree(g [][]int) []int{  num := len(g)    // 顶点数  minTree := make([]int, num)  visited := make(map[int]struct{})  // 已连通集合
  curVext := 0  // 当前遍历到的，即将放入集合内的顶点  minTree[curVext] = -1    // 将 0 号节点放入集合中  visited[curVext] = struct{}{}
  for len(visited) < num{    minWeight := math.MaxInt32    // 已连通集合的某节点 和 未连通的某节点 之间最小距离    var from, to int    for nextFromVext, _ := range(visited){  // 从已连通集合中选择一个from节点      for nextToVext:=0; nextToVext<num; nextToVext++{  // 从所有from节点的相邻节点选择一个未访问的且距离最小的to节点作为下一个生成树节点        if _, ok := visited[nextToVext]; !ok && g[nextFromVext][nextToVext] < minWeight{ // nextFromVext 到 nextToVext的距离小于 minWeight 既说明 这两个顶点是相邻的（因为他们的距离 比 MaxInt 小），又说明本nextToVext顶点比上一次的nextToVext顶点离 nextfromVext顶点近          from = nextFromVext          to = nextToVext          minWeight = g[nextFromVext][nextToVext]        }      }    }
    visited[to] = struct{}{}    minTree[to] = from  }  return minTree}

// 测试用例（用的是最短路径那个例子）func TestBuildMinTree(t *testing.T) {  m := math.MaxInt32  matrix := [][]int{    {0,5,2,m,m,m,m},    {5,0,m,1,6,m,m},    {2,m,0,6,m,8,m},    {m,1,6,0,1,2,m},    {m,6,m,1,0,m,7},    {m,m,8,2,m,0,3},    {m,m,m,m,7,3,0},  }  fmt.Println(buildMinTree(matrix))    // [-1 0 0 1 3 3 5]}