并查集C++實(shí)現(xiàn)——算法設(shè)計(jì)與分析，含代碼解釋-創(chuàng)新互聯(lián)

文章目錄

- - 什么是并查集
  - quick-find并查集
  - quick-union并查集
  - 優(yōu)化一：增加權(quán)重比較使樹變的平衡
  - 優(yōu)化二：路徑壓縮
  - 優(yōu)化過后的代碼

目前創(chuàng)新互聯(lián)已為上1000+的企業(yè)提供了網(wǎng)站建設(shè)、域名、虛擬空間、綿陽服務(wù)器托管、企業(yè)網(wǎng)站設(shè)計(jì)、滄縣網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。什么是并查集

并查集簡單來說是集合的集合，其中里層集合表示的節(jié)點(diǎn)都是可互相聯(lián)通的，并查集有兩種操作：

union連接（并）：合并兩個(gè)集合
find查詢（查）：查詢兩個(gè)元素是否在同一個(gè)集合

如下圖所示，原來的并查集為 { { 0 } , { 1 , 4 , 5 } , { 2 , 3 , 6 , 7 } } \{\{0\},\{1,4,5\},\{2,3,6,7\}\} {{0},{1,4,5},{2,3,6,7}}， { 1 , 4 , 5 } \{1,4,5\} {1,4,5}集合表示節(jié)點(diǎn)1、4、5可互相連通，經(jīng)過合并2，5節(jié)點(diǎn)后，變成了右邊的并查集，即 { 1 , 4 , 5 } \{1,4,5\} {1,4,5}和 { 2 , 3 , 6 , 7 } \{2,3,6,7\} {2,3,6,7}合并成了一個(gè)集合 { 1 , 2 , 3 , 4 , 5 , 6 , 7 } \{1,2,3,4,5,6,7\} {1,2,3,4,5,6,7}
在這里插入圖片描述
并查集的節(jié)點(diǎn)個(gè)數(shù)N可以很大，查詢操作個(gè)數(shù)M也可能很大，并且合并和查詢操作可以是混合在一起的。

接下來將介紹幾種類型的并查集，最終將介紹一個(gè)優(yōu)化的并查集，它只增加了幾行代碼就可以讓性能提高很多。

quick-find并查集

我們用一個(gè)數(shù)組id來表示并查集，如果節(jié)點(diǎn)p和節(jié)點(diǎn)q是連接的，當(dāng)且僅當(dāng)它們的id相同，例如0,5,6是相連的，它們有共同的id = 0。請?zhí)砑訄D片描述

union操作：將節(jié)點(diǎn)q和p合并，則需要遍歷一遍整個(gè)id數(shù)組，將q所在集合的所有節(jié)點(diǎn)id改成p所在集合的id，時(shí)間復(fù)雜度為 O ( N ) O(N) O(N)
find操作：判斷p和q是否相連只需要判斷它們的id是否一樣，時(shí)間復(fù)雜度為 O ( 1 ) O(1) O(1)，所以是quick-find并查集。

上述并查集的代碼如下：

#include#includeusing namespace std;
#define MAX 10004
 
class UnionFind {int id[MAX]; // 0 ~ 1000  記錄上級/老大
    int minIndex; // 范圍
    int maxIndex; // 范圍
    int cnt; //連通分量的個(gè)數(shù)
 
public :
    UnionFind() {}
    UnionFind(int minIndex, int maxIndex) {this->minIndex = minIndex;
        this->maxIndex = maxIndex;
        this->cnt = maxIndex - minIndex + 1; // 連通分量的個(gè)數(shù)
        for (int i = minIndex; i<= maxIndex ; i++) {id[i] = i;		//初始化父節(jié)點(diǎn)指向自己 
        }
    }
 
    bool isConnected(int p, int q) {//判斷p和q是否相連 
    	cout<< p<< "和"<< q<< (id[p]==id[q]?"":"不")<< "相連"<< endl; 
        return id[p] == id[q];
    }
 
    bool connect(int p, int q) {//合并x所在集合和y所在集合 
    	cout<< "合并"<< p<< "和"<< q<< endl; 
    	int pid = id[p], qid = id[q];
        if (pid == qid) 	return false; // 已經(jīng)在同一個(gè)set里面了，已經(jīng)在同一個(gè)連通分量里面了
        for(int i = minIndex; i<= maxIndex; i++){//將p所在集合的id改成q所在集合的id 
        	if(id[i] == pid)	
        		id[i] = qid;
		}
        cnt --; //連通分量少1
    }
    
    void show(){for(int i = minIndex; i<= maxIndex; i++){cout<< "i:"<< i<< " id:"<< id[i]<< endl;
		}
	} 
};

int main() {class UnionFind uf(0,9);	//定義節(jié)點(diǎn)為0-9
    uf.connect(0,5);			//連接0和5節(jié)點(diǎn) 
    uf.connect(5,6);
 	uf.connect(1,2);
 	uf.connect(2,7);
 	uf.connect(1,6);
 	uf.connect(3,8);
 	uf.connect(3,4);
 	uf.connect(4,9);
 	uf.isConnected(4,0);	//查詢4和0是否相連		
 	uf.isConnected(2,5);
 	uf.show();
}

quick-union并查集

和quick-find的id數(shù)組表示含義不一樣，quick-union的id數(shù)組表示它的父節(jié)點(diǎn)，根節(jié)點(diǎn)為 i d [ i d [ i d [ . . . i d [ i ] ] . . . ] ] ] id[id[id[...id[i]]...]]] id[id[id[...id[i]]...]]]，如下圖所示，3號節(jié)點(diǎn)的父節(jié)點(diǎn)，即id為4，根節(jié)點(diǎn)為 i d [ i d [ i d [ 3 ] ] ] = i d [ i d [ 4 ] ] = i d [ 9 ] = 9 id[id[id[3]]] = id[id[4]]=id[9]=9 id[id[id[3]]]=id[id[4]]=id[9]=9。
請?zhí)砑訄D片描述
union操作：合并p和q兩個(gè)節(jié)點(diǎn)只需要將p的根節(jié)點(diǎn)id設(shè)置成q的根節(jié)點(diǎn)id即可，例如，將3和5合并，只需要將3的根節(jié)點(diǎn)id設(shè)置成5的根節(jié)點(diǎn)id即可，時(shí)間復(fù)雜度為 O ( 1 ) O(1) O(1)，下圖展示了Union操作
請?zhí)砑訄D片描述

find操作：查詢p和q是否相連只需要判斷p和q的根節(jié)點(diǎn)是否相同，最壞的情況查詢根節(jié)點(diǎn)花費(fèi) O ( N ) O(N) O(N)，也就是節(jié)點(diǎn)連成一條線的情況

代碼表示如下：

#include#includeusing namespace std;
#define MAX 10004
 
class UnionFind {int id[MAX]; // 0 ~ 1000  記錄上級/老大
    int minIndex; // 范圍
    int maxIndex; // 范圍
    int cnt; //連通分量的個(gè)數(shù)
 
public :
    UnionFind() {}
    UnionFind(int minIndex, int maxIndex) {this->minIndex = minIndex;
        this->maxIndex = maxIndex;
        this->cnt = maxIndex - minIndex + 1; // 連通分量的個(gè)數(shù)
        for (int i = minIndex; i<= maxIndex ; i++) {id[i] = i;		//初始化父節(jié)點(diǎn)指向自己 
        }
    }
 
 	int getRoot(int p){//獲得根節(jié)點(diǎn)id
 		while(p != id[p])	p = id[p];	//逐個(gè)向上遍歷
 		return p;
	}
	
    bool isConnected(int p, int q) {//判斷p和q是否相連 
    	cout<< p<< "和"<< q<< (getRoot(p)==getRoot(q)?"":"不")<< "相連"<< endl; 
        return getRoot(p)==getRoot(q);
    }
 
    bool connect(int p, int q) {//合并x所在集合和y所在集合 
    	cout<< "合并"<< p<< "和"<< q<< endl; 
    	id[getRoot(p)] = getRoot(q);
        cnt --; //連通分量少1
    }
    
    void show(){for(int i = minIndex; i<= maxIndex; i++){cout<< "i:"<< i<< " id:"<< id[i]<< endl;
		}
	} 
};

int main() {class UnionFind uf(0,9);	//定義節(jié)點(diǎn)為0-9
    uf.connect(0,5);			//連接0和5節(jié)點(diǎn) 
    uf.connect(5,6);
 	uf.connect(1,2);
 	uf.connect(2,7);
 	uf.connect(1,6);
 	uf.connect(3,8);
 	uf.connect(3,4);
 	uf.connect(4,9);
 	uf.isConnected(4,0);	//查詢4和0是否相連		
 	uf.isConnected(2,5);
 	uf.show();
}

最后的id圖和并查集（兩棵樹）如下兩幅圖所示，可以看出來深度還是挺大的，例如查詢1和3節(jié)點(diǎn)的根節(jié)點(diǎn)需要查詢3次，比較耗時(shí)。
請?zhí)砑訄D片描述

請?zhí)砑訄D片描述

優(yōu)化一：增加權(quán)重比較使樹變的平衡

這里的trick是把矮一點(diǎn)的樹拼接到高一點(diǎn)的樹，這樣樹的高度就不會增加，查詢根節(jié)點(diǎn)就會更快

請?zhí)砑訄D片描述
我們增加一個(gè)數(shù)組contain，contain[i]表示以i為根節(jié)點(diǎn)的子樹的節(jié)點(diǎn)個(gè)數(shù)，初始條件下contain值全為1。

當(dāng)我們拼接兩棵樹時(shí)，我們比較兩棵樹的contain值，將contain值小的樹拼接到contain值大的樹上，并且大樹的contain值要加上小樹的contain值，用代碼表示如下：

int pRoot = getRoot(p);
int qRoot = getRoot(q);
if (qRoot == pRoot) {return false; // 已經(jīng)在同一個(gè)set里面了，已經(jīng)在同一個(gè)連通分量里面了
} 
else {if(contain[p] >= contain[q]) {id[qRoot] = pRoot;
        contain[pRoot] += contain[qRoot];
    } 
    else {id[pRoot] = qRoot;
        contain[qRoot] += contain[pRoot];
    }
}

這樣修改以后，樹的深度最多是 l o g ? N log\ N log?N，也就是說find操作的時(shí)間復(fù)雜度為 O ( l o g ? N ) O(log\ N) O(log?N)，union操作也為 O ( l o g ? N ) O(log\ N) O(log?N)，因?yàn)閡nion需要尋找根節(jié)點(diǎn)，這樣union操作和find操作的復(fù)雜度得到了中和。

優(yōu)化二：路徑壓縮

當(dāng)我們查詢了一次節(jié)點(diǎn)p之后，我們求出了它的根節(jié)點(diǎn)root，我們可以p直接和root相連，這樣我們下一次查找p的根節(jié)點(diǎn)就只要 O ( 1 ) O(1) O(1)的時(shí)間了，我們就只需要在find操作里加兩行代碼即可，表示將當(dāng)前節(jié)點(diǎn)與其父節(jié)點(diǎn)相連，直到與其根節(jié)點(diǎn)相連。

int getRoot(int p) {//采用遞歸的方式
    if (id[p] == p) {//自己就是根節(jié)點(diǎn) 
    	return p;  
    } 
    else {int d = id[p];
        int root = getRoot(d);
        if (d != root) {id[p] = root;		//將當(dāng)前節(jié)點(diǎn)的id設(shè)置成根節(jié)點(diǎn) 
            contain[d] -= contain[p]; 	//因?yàn)閐的子樹移到了根節(jié)點(diǎn)，所以要將d的contain減去p的contain 
    	}
    return root;
    }
}

初始的樹如下所示：
請?zhí)砑訄D片描述
依次查詢節(jié)點(diǎn)9，6，3以后，將它們移到根節(jié)點(diǎn)下，整棵樹的高度就比之前少了很多，變得更平坦了。

可以驗(yàn)證當(dāng)有 1 0 9 10^9 109次union操作和 1 0 9 10^9 109次find操作，最普通的并查集需要花費(fèi)30多年，而僅加上幾行代碼的優(yōu)化過的并查集只需要6秒，由此可見一個(gè)性能好的算法是多么重要。

優(yōu)化過后的代碼

#include#includeusing namespace std;
#define MAX 10004
 
class UnionFind {int id[MAX]; // 
    int contain[MAX]; // 包含多少節(jié)點(diǎn) 
    int minIndex; // 范圍
    int maxIndex; // 范圍
    int cnt; //連通分量的個(gè)數(shù)
 
public :
    UnionFind() {}
    UnionFind(int minIndex, int maxIndex) {this->minIndex = minIndex;
        this->maxIndex = maxIndex;
        this->cnt = maxIndex - minIndex + 1; // 連通分量的個(gè)數(shù)
        for (int i = minIndex; i<= maxIndex ; i++) {id[i] = i;
            contain[i] = 1;
        }
 
    }
 
    int getRoot(int p) {//采用遞歸的方式 
        if (id[p] == p) {//自己就是根節(jié)點(diǎn) 
            return p;  
        } 
		else {int d = id[p];
            int root = getRoot(d);
            if (d != root) {id[p] = root;		//將當(dāng)前節(jié)點(diǎn)的id設(shè)置成根節(jié)點(diǎn) 
                contain[d] -= contain[p]; 	//因?yàn)閐的子樹移到了根節(jié)點(diǎn)，所以要將d的contain減去p的contain 
            }
            return root;
        }
    }
 
    bool isConnected(int p, int q) {return getRoot(q) == getRoot(p);
    }
 
    bool connect(int p, int q) {int pRoot = getRoot(p);
		int qRoot = getRoot(q);
		if (qRoot == pRoot) {return false; // 已經(jīng)在同一個(gè)set里面了，已經(jīng)在同一個(gè)連通分量里面了
		} 
		else {if(contain[p] >= contain[q]) {id[qRoot] = pRoot;
		        contain[pRoot] += contain[qRoot];
		    } 
		    else {id[pRoot] = qRoot;
		        contain[qRoot] += contain[pRoot];
		    }
		}
        cnt --; //連通分量少1
    }
 
    int getCnt() {return cnt;
    }
 
    void show(){cout<< "i\tid\tcontain"<< endl;
    	for(int i = minIndex; i<= maxIndex; i++){cout<< i<< "\t"<< id[i]<< "\t"<< contain[i]<< endl;
		}
	} 
};
 
int main() {class UnionFind uf(1,6);	//定義節(jié)點(diǎn)為1-6 
    uf.connect(3,4);			//連接3和4節(jié)點(diǎn) 
    uf.connect(5,4);
 	uf.connect(1,2);
 	uf.connect(6,5);
 	uf.connect(1,5);
 	uf.getRoot(4);				//查找4的根節(jié)點(diǎn) 
 	uf.getRoot(2);
	uf.show();
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站欄目：并查集C++實(shí)現(xiàn)——算法設(shè)計(jì)與分析，含代碼解釋-創(chuàng)新互聯(lián)
分享URL：http://weahome.cn/article/ddsosj.html

真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

并查集C++實(shí)現(xiàn)——算法設(shè)計(jì)與分析，含代碼解釋-創(chuàng)新互聯(lián)

其他資訊

網(wǎng)站制作

企業(yè)服務(wù)

網(wǎng)站建設(shè)

服務(wù)器托管