并查集（UnionFind）
并查集和其他樹形結構不一樣，是由孩子指向父親，它解決了一些連接問題，怎么才能確定兩個點是否相連呢？并查集可以非常快的確定兩個點是否連接。
如何確定連個點是否連接呢？
我們可以用一個數組表示，對于0到9每個不同的編號可以表示不同的對象，這里可以看作一個點，而編號對應的不同的元素可以表示不同的集合，其中[0，2，4，6，8]表示一個集合。這樣就可以表示連接問題了，0和2就是表示相連接，因為它們在一個集合，0和1因不在一個集合所以不連接。
對于一組數據并查集主要支持兩個動作：
- isConnected(p,q)：查詢元素p和q是否在一個集合
- unionElements(p,q)：合并元素p和q的集合
Code
#pragma once
class UF {
private:
virtual const int getSize() const noexcept = 0;
virtual bool isConnected(int p, int q) = 0;
virtual void unionElements(int p, int q) = 0;
};
#pragma once
#include "UF.h"
#include<cassert>
class UnionFind1 : public UF {
private:
int *id;
int size;
public:
UnionFind1(int capacity) {
id = new int[capacity];
size = capacity;
for (int i = 0; i < size; ++i) {
id[i] = i; //初始化不同的元素表示不同的集合都不相連
}
}
const int getSize() const noexcept {
return size;
}
//返回p所在的集合
int find(int p) {
assert(p >= 0 && p < size);
return id[p];
}
//判斷是否相連
bool isConnected(int p, int q) {
return find(p) == find(q);
}
//合并集合
void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID) {
return;
}
for (int i = 0; i < size; ++i) {
if (id[i] == pID) {
id[i] = qID; //讓兩個集合都相同就行了
}
}
}
};
優化unionElements
從代碼中可以看到：
- unionElements的時間復雜度是O(n)
- isConnected的時間復雜度是O(1)
將每個元素，看做是一個節點，每個節點指向它的父節點，而根節點指向自己。如果我們進行unionElements(4,3)操作，那么就是讓4索引的元素為3。同在一個樹下面就是同一個集合表示相連。
Code
#pragma once
#include "UF.h"
#include<cassert>
class UnionFind2 : public UF {
private:
int *parent;
int size;
public:
UnionFind2(int capacity) {
parent = new int[capacity];
size = capacity;
for (int i = 0; i < size; ++i) {
parent[i] = i;
}
}
const int getSize() const noexcept {
return size;
}
int find(int p) {
assert(p >= 0 && p < size);
while (p != parent[p]) {
p = parent[p];
}
return p;
}
bool isConnected(int p, int q) {
return find(p) == find(q);
}
void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
parent[pRoot] = qRoot;
}
};
基于size的優化
由于對真正合并那兩個元素所在樹的形狀沒有做判斷，很多時候會增加樹的高度。
優化方法：節點個數小的那個節點去指向節點個數多個那個根節點。
Code
#ifndef UNION_FIND_UNIONFIND3_H
#define UNION_FIND_UNIONFIND3_H
#include "UF.h"
#include <cassert>
class UnionFind3 : public UF {
private:
int *parent;
int *sz;
int size;
public:
UnionFind3(int capacity) {
parent = new int[capacity];
sz = new int[capacity];
size = capacity;
for (int i = 0; i < size; ++i) {
parent[i] = i;
sz[i] = 1;
}
}
int getSize() {
return size;
}
int find(int p) {
assert(p >= 0 && p < size);
while (p != parent[p]) {
p = parent[p];
}
return p;
}
bool isConnected(int p, int q) {
return find(p) == find(q);
}
void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
if (sz[pRoot] < sz[qRoot]) {
parent[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
} else {
parent[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
}
};
#endif //UNION_FIND_UNIONFIND3_H
基于rank的和優化
如果基于size優化會增加樹的高度
如果基于rank的優化rank[i]表示根節點為i的樹的高度
Code
#ifndef UNION_FIND_UNIONFIND4_H
#define UNION_FIND_UNIONFIND4_H
#include "UF.h"
#include <cassert>
class UnionFind4 : public UF {
private:
int *parent;
int *rank;
int size;
public:
UnionFind4(int capacity) {
parent = new int[capacity];
rank = new int[capacity];
size = capacity;
for (int i = 0; i < size; ++i) {
parent[i] = i;
rank[i] = 1;
}
}
int getSize() {
return size;
}
int find(int p) {
assert(p >= 0 && p < size);
while (p != parent[p]) {
p = parent[p];
}
return p;
}
bool isConnected(int p, int q) {
return find(p) == find(q);
}
void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
if (rank[pRoot] < rank[qRoot]) {
parent[pRoot] = qRoot;
} else if (rank[pRoot] > rank[qRoot]) {
parent[qRoot] = pRoot;
} else {
parent[qRoot] = pRoot;
rank[pRoot] += 1;
}
}
};
#endif //UNION_FIND_UNIONFIND4_H
路徑壓縮
優化方法一
優化方法二
Code
#pragma once
#include "UF.h"
#include<cassert>
class UnionFind : public UF {
public:
UnionFind(int cap) : size(cap) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; ++i) {
parent[i] = i;
rank[i] = 1;
}
}
~UnionFind() noexcept {
delete[] parent;
parent = nullptr;
}
const int getSize() const noexcept override {
return size;
}
//查詢元素p和q是否在一個集合
bool isConnected(int p, int q) override {
return find(p) == find(q);
}
//合并元素p和q的集合
void unionElements(int p, int q) override {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
//就把其中一個的根節點掛到另一個的根上
if (rank[pRoot] < rank[qRoot]) {
parent[pRoot] = qRoot; //高度小的根節點指向高度大的根節點，從而減少樹的高度，防止退化
} else if (rank[qRoot] < rank[pRoot]) {
parent[qRoot] = pRoot;
} else {
parent[qRoot] = pRoot;
++rank[pRoot];
}
}
private:
//查找元素p對應的集合編號，O(h)復雜度, h為樹的高度
//根節點就是集合編號，且根節點指向自己，索引 p == parent[p]
int find(int p) {
assert(p >= 0 && p < size);
while (p != parent[p]) {
parent[p] = parent[parent[p]]; //路徑壓縮，讓p這個節點指向它父親的父親
p = parent[p];
}
return p;
}
//遞歸版路徑壓縮，讓集合中所有節點指向根節點
int recFind(int p) {
assert(p >= 0 && p < size);
if (p != parent[p]) {
parent[p] = find(parent[p]);
}
return parent[p];
}
private:
int *parent;
int *rank;
int size;
};
浙公網安備 33010602011771號