图的储存与并查集的实现

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

图的类型有很多,常见的有:无向图有向图加权图

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

图的定义和相关术语

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

相关的定义:

  • 顶点
  • :顶点之间的连接线称为边
  • 路径:从一个顶点到另一个顶点之间经过的所有顶点的集合。
  • 路径长度:一条路径上经过的边的数量。
  • :起点和终点为同一个顶点的路径。。
  • 负权环:在 加权图 中,如果一个环的所有边的权重加起来为负数,我们就称之为「负权环」。
  • 连通性:两个不同顶点之间存在至少一条路径,则称这两个顶点是连通的。
  • 顶点的度:度适用于 无向图 ,指的是和该顶点相连接的所有边数
  • 顶点的入度:入度适用于 有向图 ,一个顶点的入度指与顶点相连的边指向该顶点的个数。
  • 顶点的出度:出度适用于 有向图 ,一个顶点的出度指与顶点相连的边以该顶点为起点的个数。

图的相关知识点:

  • 并查集( Union Find )数据结构
  • 「图」的深度优先搜索算法
  • 「图」的广度优先搜索算法
  • 最小生成树相关定理和算法
    • 切分定理
    • Kruskal 算法
    • Prim 算法
  • 单源最短路径相关算法
    • Dijkstra 算法
    • Bellman-Ford 算法
    • 拓扑排序之 Kahn 算法

图的存储

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

矩阵存图法

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

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

更具体地,我们一般使用 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 并查集 - 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;
}
}

测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
}
}

测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 函数进行优化

实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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 函数进行优化。

1
2
3
4
5
// 相对于 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 函数是查找函数,查找的同时,路径压缩。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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))$

并查集的实现 总结

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

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

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

题目 - 并查集

参考文献

JavaScript 算法
作者:Kart Jim
链接:https://github.com/can-dy-jack/delicate/2022/12/12/algorithm/图/
来源:Hexo
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 许可协议。著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
长风破浪会有时,直挂云帆济沧海