> 文章列表 > 图论 Union-Find 并查集算法

图论 Union-Find 并查集算法

图论 Union-Find 并查集算法

union-find API:

class UF {
public:/* 将 p 和 q 连接 */void union(int p, int q);/* 判断 p 和 q 是否连通 */bool connected(int p, int q);/* 返回图中有多少个连通分量 */int count();
};

连通性概念

    触点:每个单独的不与任何点相连的点叫做触点

    连通分量:简称分量,不存在连接关系的触点和连通在一起的触点的集合都是连通分量

    等价关系:处于同一连通分量的触点为等价关系,即他们是连通的

0~9 任意两个不同的点都不连通,调用 connected 都会返回 false,连通分量为 10 个。

如果现在调用 union(0, 1),那么 0 和 1 被连通,连通分量降为 9 个。

再调用 union(1, 2),这时 0,1,2 都被连通,调用 connected(0, 2) 也会返回 true,连通分量变为 8 个

好啦现在大概知道什么是连通性和连通分量了吧

如果某两个节点被连通,则让其中的(任意)一个节点的根节点接到另一个节点的根节点上

这里connect的实现思路就是把连通的父类之间相连接

class UF {
private:int count = 0; // 记录连通分量int* parent; // 节点x的父节点是parent[x]public:UF(int n) {this->count = n;parent = new int[n];for(int i = 0; i < n; i++) {parent[i] = i;}}void Union(int p, int q) {int rootP = find(p);int rootQ = find(q);if(rootP == rootQ) return;parent[rootP] = rootQ;count--;}bool connected(int p, int q) {int rootP = find(p);int rootQ = find(q);return rootP == rootQ;}int find(int x) {// 根节点的parent[x] == x,层层向上找就好啦while(parent[x] != x) {x = parent[x];}return x;}

(只是一种connect方式,充分不必要,不要老想着问为什么不直接点对点接,有些东西就是因为直接做做不了,才退而求其次间接去做)

大体思路就是这样,但是这么做太直接,无法避免不平衡树(退化成链表)的出现

下面就是优化算法的时间复杂度 => 就是在想法子来降低树的高度

1. 平衡性优化

主要就是把小一些的树接到大一些的树下面,引入“重量”来实现这一目的

通过比较树的重量,就可以保证树的生长相对平衡,树的高度大致在 logN 这个数量级

class UF {
private:int count = 0; // 记录连通分量int* parent; // 节点x的父节点是parent[x]int* size;public:UF(int n) {this->count = n;parent = new int[n];size = new int [n];for(int i = 0; i < n; i++) {parent[i] = i;size[i] = 1;}}void Union(int p, int q) {int rootP = find(p);int rootQ = find(q);if(rootP == rootQ) return;
//        小树接到大树下面if(size[rootP] > size[rootQ]) {parent[rootQ] = rootP;size[rootP] += size[rootQ];}else {parent[rootP] = rootQ;size[rootQ] += size[rootP];}count--;}bool connected(int p, int q) {int rootP = find(p);int rootQ = find(q);return rootP == rootQ;}int find(int x) {// 根节点的parent[x] == x,层层向上找就好啦while(parent[x] != x) {x = parent[x];}return x;}int getCount() { return count; }};

2. 路径压缩

我们关注的其实就只有根节点 => 树压的越低越好

int find(int x) {// 根节点的parent[x] == x,层层向上找就好啦if(parent[x] != x) parent[x] = find(parent[x]);return parent[x];}

 其实如果使用路径压缩技巧,那么 size 数组的平衡优化就不是特别必要了

完整代码如下:

class UF {
private:int count = 0; // 记录连通分量int* parent; // 节点x的父节点是parent[x]int* size;public:UF(int n) {this->count = n;parent = new int[n];size = new int [n];for(int i = 0; i < n; i++) {parent[i] = i;size[i] = 1;}}void Union(int p, int q) {int rootP = find(p);int rootQ = find(q);if(rootP == rootQ) return;
//        小树接到大树下面if(size[rootP] > size[rootQ]) {parent[rootQ] = rootP;size[rootP] += size[rootQ];}else {parent[rootP] = rootQ;size[rootQ] += size[rootP];}count--;}bool connected(int p, int q) {int rootP = find(p);int rootQ = find(q);return rootP == rootQ;}int find(int x) {// 根节点的parent[x] == x,层层向上找就好啦if(parent[x] != x) parent[x] = find(parent[x]);return parent[x];}int getCount() { return count; }};