图的储存与并查集的实现

本文为学习笔记，学习资料来源如下：
作者：爱学习的饲养员
链接：https://leetcode.cn/leetbook/read/graph/npniph/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

图的类型有很多，常见的有：无向图、有向图、加权图。

无向图的图中任意两个顶点之间的边都是没有方向的。
有向图的图中任意两个顶点之间的边都是有方向的。
加权图的图中的每条边都有一个权重。

图的定义和相关术语

「图」是由顶点和边组成的一种非线形数据结构。

图的存储

在程序中运用图论相关算法的第一步，我们需要先学会如何把图储存起来。

矩阵存图法

图中的顶点我们已经编好了号，那么我们需要储存的和图相关的信息，就只剩下点与点之间的连边了。

一个很直观的想法就是用一个二维数组来存图，下标代表点，值代表连边的情况。这就是所谓的矩阵存图法，也被称作为邻接矩阵存图法。

更具体地，我们一般使用 bool 数组来储存点与点之间的连边信息：

如果 con[i][j] 的值为 true ，表示点 i 与点 j 之间连了一条从 i 指向 j 的边。
如果 con[i][j] 的值为 false ，表示点 i 与点 j 之间没有连边。

基本操作的复杂度：

添加一条边的时间复杂度为 $\Theta(1)$ 。
判断两个点之间是否有边相连的时间复杂度为 $\Theta(1)$ 。
遍历一个点的所有出边的复杂度为 $\Theta(n)$

矩阵存图法各种操作的时间复杂度相对来说都较为优秀，但是其劣势在于：存下一个图需要 $O(n^2)$ 的空间复杂度，这在面对点与点之间的连边数远远小于 $\Theta(n^2)$ 的稀疏图时，就有很多空间被浪费了。

我们之前的讨论，针对的是无权有向图，那么如果面对的是有权图，或者无向图，我们该如何进行存储呢？

对于有权图的情况：我们只需要将 bool 数组改为 int 数组，两点之间有连边，就将对应元素的值改为边权即可。当然这种情况下，需要将数组初始化为一个不可能的边权（部分题目存在边权为 0 的情况）
对于无向图的情况：只需 con[i][j] = con[j][i] = true

邻接表存图法

矩阵存图的最大的劣势，就是在面对稀疏图时，有很多空间没有储存有效信息（对于一个图，我们往往更加关注哪些点之间有连边，而不关注哪些点之间没有连边），被浪费掉了。一个优化的思路是：我们不再考虑储存每一个点对之间的连边信息，而只考虑那些有连边的点对。这样我们就能够保证所储存下来的信息都会是有效的。

针对上述思路，对于一个有 n 的点的图，我们可以利用 n 个链表，第 i 个链表里存着所有从 i 直接连向的点。

基本操作的复杂度：

添加一条边需要新建一个结构体，并且插入链表中，时间复杂度为 $\Theta(1)$ 如果我们添加的是无向边，那么需要添加两次。
判断两个点之间是否有边相连：如果我们想要知道图中是否存在一条从 i 连向 j 的边，那么我们需要遍历点 i 的所有出边，判断终点是否为 j 。因此，判断两个点之间是否有边相连的时间复杂度，与遍历一个点的所有出边的时间复杂度相同，为 $\Theta(出度)$
遍历一个点的所有出边时间复杂度为 $\Theta(出度)$ 。从实现上来看，遍历一个点的所有出边，等价于遍历第 i 个节点对应的链表。

由于邻接表只储存了连接的边的信息，所以其空间复杂度为 $\Theta(m)$ （一般我们用 m 来表示图中边的数量）

链式前向星存图法

链式前向星存图和邻接表存图的方式总体思路是相同的，只是在实现的方式上有所不同。链式前向星更像是数组模拟链表的一种运用。 在算法竞赛中广泛应用。

链式前向星存图与邻接表存图，虽然实现方式差异较大，但实际的时间复杂度是一样的。

并查集

「并查集」的主要作用是用来解决网络中的连通性。

父节点：顶点的直接父亲节点。
根节点：没有父节点的节点，本身可以视为自己的父节点。

设计并查集数据结构：

union 函数：合并两个顶点，并将他们的根结点保持一致。
find 函数：找到给定顶点的根结点。

并查集有两个实现方式：

Quick Find ：它指的是实现「并查集」时，find 函数时间复杂度很低为 O(1)，让 union 函数就需要承担更多的责任，它的时间复杂度为 O(N)。
Quick Union ：它指的是实现「并查集」时，相对于 Quick Find 的实现方式，我们通过降低 union 函数的职责来提高它的效率，但同时，我们也增加了 find 函数的职责。

Quick Find

// 并查集 - Quick Find 的实现
class UnionFind {
  constructor(len) {
    this.root = Array(len)
      .fill(0)
      .map((_, i) => i);
  }
  find(x) {
    // 主要工作都分配给了 union函数，其已经将对应的根元素分好
    return this.root[x];
  }
  union(x, y) {
    let rootx = this.find(x),
      rooty = this.find(y);
    if (rootx !== rooty) {
      // 如果根元素不同，则将根元素换为 y 的
      for (let i = 0; i < this.root.length; i++) {
        if (this.root[i] === rootx) this.root[i] = rooty;
      }
    }
  }
  // 判断是否联通
  connected(x, y) {
    return this.find(x) == this.find(y);
  }

  // 测试专用
  show() {
    return this.root;
  }
}

测试：

const uf = new UnionFind(10);
// 1-2-5-6-7 3-8-9 4
uf.union(1, 2);
uf.union(2, 5);
uf.union(5, 6);
uf.union(6, 7);
uf.union(3, 8);
uf.union(8, 9);
uf.show(); // [ 0, 7, 7, 9, 4, 7, 7, 7, 9, 9 ]
uf.connected(1, 5); // true
uf.connected(7, 5); // true
uf.connected(4, 9); // false
uf.union(9, 4);
uf.connected(4, 9); // true

Quick Union

class UnionFind {
  constructor(len) {
    this.root = Array(len)
      .fill(0)
      .map((_, i) => i);
  }
  // 递归寻找根节点
  find(x) {
    while (x !== this.root[x]) x = this.root[x];
    return x;
  }
  // 将根节点划归为一个
  union(x, y) {
    let rootx = this.find(x),
      rooty = this.find(y);
    if (rootx !== rooty) this.root[rootx] = rooty;
  }
  connected(x, y) {
    return this.find(x) === this.find(y);
  }

  // 测试专用
  show() {
    return this.root;
  }
}

测试：

const uf = new UnionFind(10);
// 1-2-5-6-7 3-8-9 4
uf.union(1, 2);
uf.union(2, 5);
uf.union(5, 6);
uf.union(6, 7);
uf.union(3, 8);
uf.union(8, 9);
uf.show(); // [ 0, 2, 5, 8, 4, 6, 7, 7, 9, 9 ]
uf.connected(1, 5); // true
uf.connected(7, 5); // true
uf.connected(4, 9); // false
uf.union(9, 4);
uf.connected(4, 9); // true

	构造函数	find 函数	union 函数	connected 函数
Quick Find 时间复杂度	$O(N)$	$O(1)$	$O(N)$	$O(1)$
Quick Union 时间复杂度	$O(N)$	$O(H)$	$O(H)$	$O(H)$

N 为顶点的个数，H 树的高度。

总体来说，Quick Union 是比 Quick Find 更加高效的。

按秩合并的「并查集」

我们已经实现了 2 种「并查集」。但它们都有一个很大的缺点，这个缺点就是通过 union 函数连接顶点之后，可能所有顶点连成一条线形成，这就是我们 find 函数在最坏的情况下的样子。

解决方案便是按秩合并。这里的「秩」可以理解为「秩序」。之前我们在 union 的时候，我们是随机选择 x 和 y 中的一个根节点/父节点作为另一个顶点的根节点。但是在「按秩合并」中，我们是按照「某种秩序」选择一个父节点。

这里的「秩」指的是每个顶点所处的高度。我们每次 union 两个顶点的时候，选择根节点的时候不是随机的选择某个顶点的根节点，而是将「秩」大的那个根节点作为两个顶点的根节点，换句话说，我们将低的树合并到高的树之下，将高的树的根节点作为两个顶点的根节点。这样，我们就避免了所有的顶点连成一条线，这就是按秩合并优化的「并查集」。

所以，按秩排序根本上就是对 Quick Union 中的 union 函数进行优化

实现代码：

class UnionFind {
  constructor(len) {
    // 保存数据及其对应的父节点
    this.root = Array(len).fill(0).map((_, i) => i);
    // 保存高度
    this.rank = Array(len).fill(1);
  }
  find(x) {
    while(x !== this.root[x]) x = this.root[x];
    return x;
  }
  union(x, y) {
    let rootx = this.find(x), rooty = this.find(y);
    if(rootx !== rooty) {
      if(this.rank[rootx] > this.rank[rooty]) {
        this.root[rooty] = rootx;
      } else if(this.rank[rootx] < this.rank[rooty]) {
        this.root[rootx] = rooty;
      } else { // ===
        this.root[rootx] = rooty;
        this.rank[rooty] += 1;
      }
    }
  }
  connected(x, y) {
    return this.find(x) === this.find(y)
  }
}

	构造函数	find 函数	union 函数	connected 函数
时间复杂度	$O(N)$	$O(logN)$	$O(logN)$	$O(logN)$

路径压缩优化的「并查集」

从前面的「并查集」实现方式中，我们不难看出，要想找到一个元素的根节点，需要沿着它的父亲节点的足迹一直遍历下去，直到找到它的根节点为止。如果下次再查找同一个元素的根节点，我们还是要做相同的操作。

如果我们在找到根节点之后，将所有遍历过的元素的父节点都改成根节点，那么我们下次再查询到相同元素的时候，我们就仅仅只需要遍历两个元素就可以找到它的根节点了，这是非常高效的实现方式。可以使用递归算法，这种优化我们称之为「路径压缩」优化，它是对 Quick Union 中的 find 函数进行优化。

// 相对于 Quick Union 的代码，只需要更改 find 函数
find(x) {
    if (x == this.root[x])  return x;
    return this.root[x] = this.find(this.root[x]);
}

	构造函数	find 函数	union 函数	connected 函数
时间复杂度	$O(N)$	$O(logN)$	$O(logN)$	$O(logN)$

基于路径压缩的按秩合并优化的「并查集」

这个优化就是将「路径压缩优化」和「按秩合并优化」合并后形成的「并查集」的实现方式。
union 函数是合并的函数，合并的时候按秩合并。find 函数是查找函数，查找的同时，路径压缩。

代码：

class UnionFind {
  constructor(len) {
    this.root = Array(len)
      .fill(0)
      .map((_, i) => i);
    this.rank = Array(len).fill(1);
  }
  // 路径压缩优化版本的 find 函数
  find(x) {
    if (x === this.root[x])  return x;
    return this.root[x] = this.find(this.root[x]);
  }
  // 按秩合并优化的 union 函数
  union(x, y) {
    let rootx = this.find(x), rooty = this.find(y);
    if(rootx !== rooty) {
      if(this.rank[rootx] > this.rank[rooty]) {
        this.root[rooty] = rootx;
      } else if(this.rank[rootx] < this.rank[rooty]) {
        this.root[rootx] = rooty;
      } else { // ===
        this.root[rootx] = rooty;
        this.rank[rooty] += 1;
      }
    }
  }
  connected(x, y) {
    return this.find(x) === this.find(y);
  }
}

	构造函数	find 函数	union 函数	connected 函数
时间复杂度	$O(N)$	$O(\alpha(N))$	$O(\alpha(N))$	$O(\alpha(N))$

并查集的实现总结

在「并查集」数据结构中，其中心思想是将所有连接的顶点，无论是直接连接还是间接连接，都将他们指向同一个父节点或者根节点。此时，如果要判断两个顶点是否具有连通性，只要判断它们的根节点是否为同一个节点即可。

在「并查集」数据结构中，它的两个灵魂函数，分别是 find 和 union 。find 函数是为了找出给定顶点的根节点。 union 函数是通过更改顶点根节点的方式，将两个原本不相连接的顶点表示为两个连接的顶点。对于「并查集」来说，它还有一个重要的功能性函数 connected。它最主要的作用就是检查两个顶点的「连通性」。find 和 union 函数是「并查集」中必不可少的函数。connected 函数则需要根据题目的意思来决定是否需要。

「并查集」的代码是高度模版化的。熟记「基于路径压缩+按秩合并的并查集」的实现代码。