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

发表于 更新于 分类于
本文字数： 4.9k 阅读时长 ≈ 9 分钟

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

简介

并查集（disjoint set，也称为union-find set或merge-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;
}

查找优化

针对并查集中查找元素根节点函数Find有2种优化方式：

  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

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

合并优化

有两种方式可作用于子集合并操作，通过size或rank来优化

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

相关阅读