[数据结构][图算法]并查集

之前在数据结构-图5中实现了图的最小生成树,主要参考的是《大话数据结构》中的相关内容。在Kruskal算法实现中通过函数Find就能检查两个分量之间是否相连,效率很高,当时觉得这种实现很神奇,今天才发现这是一种专门的数据结构实现 - 并查集(disjoint set

简介

并查集(disjoint set,也称为union-find setmerge-find set)是一个元素集合,保存了划分为若干个不相交(不重叠)的元素子集

并查集的操作效率接近常量时间,其操作包括

  • 添加新的集合
  • 合并现有的集合
  • 确定元素是否在同一集合中

从树结构的角度看,并查集就是一个森林,每个子集就是一颗树

在图最小生成树的Kruskal算法实现中,并查集起着关键作用

实现

并查集中每个元素包含了两个成员:一是元素ID,二是父指针

利用一个一维数组表示元素集,数组下标表示每个元素,数组值表示父指针

  • 最开始的数组值可以置为空(或者赋值为当前下标值),表示自己就是根节点
  • 比较两个元素是否在同一集合中,可以通过函数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
void MiniSpanTree_Kruskal(GraphAdjList G) {
...
// 并查集,数组下标表示顶点,赋值表示父节点下标
int parent[MAXVEX] = {};

...
...
// 升序遍历
for (i = 0; i < G.numEdges; i++) {
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
// 判断两个分量是否同属一个
if (n != m) {
parent[n] = m;
}
}
}

int Find(int *parent, int f) {
// 遍历分量
while (parent[f] > 0) {
f = parent[f];
}

return f;
}

查找优化

针对并查集中查找元素根节点函数Find2种优化方式:

  1. 路径压缩(path compression
  2. 路径减半(path halving

路径压缩

其实现方式是将树结构压平,使得子节点指针均指向根节点,这样能够加快元素的查询操作

1
2
3
4
function Find(x)
if x.parent != x
x.parent := Find(x.parent)
return x.parent

路径减半

其实现方式是将节点父指针指向祖父节点

1
2
3
4
5
function Find(x)
while x.parent != x
x.parent := x.parent.parent
x := x.parent
return x

注意:此时根节点父指针应该指向自己

合并优化

有两种方式可作用于子集合并操作,通过sizerank来优化

union by rank

秩(rank)优化作用于子集合并操作,总是将较短树附加到较高树的根上。因此,生成的树不比原始树高。在高度相等的情况下,生成的树才会比原始树高一个节点

在每个元素中再添加一个成员rank。一个集合最初只有一个元素,所以秩为零

  • 如果两个集合具有相同的秩,任选其中一个作为根节点,结果集的秩加1
  • 如果两个集合具有不同的秩,较大rank值的子集作为根节点,结果集的秩不变
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function Union(x, y)
xRoot := Find(x)
yRoot := Find(y)

// x and y are already in the same set
if xRoot == yRoot
return

// x and y are not in same set, so we merge them
if xRoot.rank < yRoot.rank
xRoot, yRoot := yRoot, xRoot // swap xRoot and yRoot
// merge yRoot into xRoot
yRoot.parent := xRoot
if xRoot.rank == yRoot.rank:
xRoot.rank := xRoot.rank + 1

union by size

大小(size)优化的原理和rank优化类似,通过新成员size保存每个子集的元素个数。每次都选择较大size的子集作为根节点,并加上另一个子集的size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function Union(x, y)
xRoot := Find(x)
yRoot := Find(y)

// x and y are already in the same set
if xRoot == yRoot
return

// x and y are not in same set, so we merge them
if xRoot.size < yRoot.size
xRoot, yRoot := yRoot, xRoot // swap xRoot and yRoot

// merge yRoot into xRoot
yRoot.parent := xRoot
xRoot.size := xRoot.size + yRoot.size

类实现

下面创建类来实现并查集,通过路径压缩和rank合并来优化

  • 新建结构体disjoint_set_element,保存父指针和rank
  • 新建类DisjointSet,保存元素数组,实现查找和合并操作
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//
// Created by zj on 19-10-31.
//

#ifndef CPLUSPLUS_DISJOINSET_H
#define CPLUSPLUS_DISJOINSET_H

#include <iostream>
#include <memory>

typedef struct disjoint_set_element {
int parentPoint;
int rank;
} ds_element;


class DisjointSet {
public:
DisjointSet(const int num);

~DisjointSet();

/**
* 利用路径压缩优化
* @param x 起始节点
* @return 根节点
*/
int find(int x);

/**
* 子集合并,利用rank进行优化
* @param x 根节点
* @param y 根节点
* @return 连接成功,返回true;连接失败或者原节点在同一个子集中,返回false
*/
bool join(int x, int y);

/**
* 返回集合数
*/
int getSetNum() {
return this->num;
}

private:
ds_element *elements;
// 子集数
int num;
};


#endif //CPLUSPLUS_DISJOINSET_H

//
// Created by zj on 19-10-31.
//

#include "DisjointSet.h"

DisjointSet::DisjointSet(const int num) {
elements = new ds_element[num];
this->num = num;

for (int i = 0; i < num; i++) {
elements[i].rank = 0;
elements[i].parentPoint = i;
}
}

DisjointSet::~DisjointSet() {
delete[] elements;
}

int DisjointSet::find(int x) {
if (elements[x].parentPoint != x) {
elements[x].parentPoint = find(elements[x].parentPoint);
}

return elements[x].parentPoint;
}

bool DisjointSet::join(int x, int y) {
if (x == y) {
return false;
}

// 保证节点x的rank大于等于节点y
if (elements[x].rank < elements[y].rank) {
int tmp = x;
x = y;
y = tmp;
}

elements[y].parentPoint = x;
if (elements[x].rank == elements[y].rank) {
elements[x].rank += 1;
}

this->num--;
return true;
}

Kruskal算法实现

通过上节定义的并查集完成Kruskal算法,分别通过邻接矩阵和邻接表实现

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
32
33
34
35
36
37
38
39
40
41
42
43
44
void AdjacencyTableUndirectedGraph::MiniSpanTree_Kruskal(GraphAdjList G) {
int i, j, k, n, m;
EdgeNode *e;
std::array<Edge, MAXEDGE> edges = {};
DisjointSet disjointSet(G.numVertexes);

// 将边集赋值给edges
k = 0;
for (i = 0; i < G.numVertexes; i++) {
e = G.adjList[i].firstEdge;

while (e != nullptr) {
if (e->adjvex > i) {
Edge edge;
edge.begin = i;
edge.end = e->adjvex;
edge.weight = e->weight;

edges[k] = edge;
k++;
}

e = e->next;
}
}
// 按权值升序排序
std::sort(edges.begin(), edges.begin() + G.numEdges, less_second);

int weight = 0;
// 升序遍历
for (i = 0; i < G.numEdges; i++) {
n = disjointSet.find(edges[i].begin);
m = disjointSet.find(edges[i].end);
if (disjointSet.join(n, m)) {
printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
weight += edges[i].weight;
}
}
cout << "MST权值和为:" << weight << endl;
}

bool AdjacencyTableUndirectedGraph::less_second(Edge x, Edge y) {
return x.weight < y.weight;
}

完整代码参考:zjZSTU/GraphLib

相关阅读