并查集是簡單的數(shù)據(jù)結(jié)構(gòu)，學(xué)會并查集，為圖打好基礎(chǔ)。
并查集的概念
是樹狀的數(shù)據(jù)結(jié)構(gòu)，用于處理相交集合的合并與查詢
通常用森林表示，一片森林表示一個集合
并查集一般需要完成
- 查找元素屬于哪個集合
- 查看兩個元素是否屬于同一個集合
- 將兩個集合歸并成一個集合
- 集合的個數(shù)
并查集的原理 ?
假設(shè)有10個人，用集合表示為{0，1，2，3，4，5，6，7，8，9}
我們用數(shù)組表示這十個人
- 數(shù)組的下標(biāo)表示人的編號
- 數(shù)組的內(nèi)容表示每個人認(rèn)識其中人的數(shù)目 （-1 表示只認(rèn)識自己)
表示為10片森林
經(jīng)過一段時間后，他們形成三個小團(tuán)體，s1{0,6,7,8}? s2{1,4,9} s3{ 2,3,5}
利用并查集表示
- 數(shù)組的下標(biāo)對應(yīng)集合中元素的編號
- 數(shù)組中如果為負(fù)數(shù)，負(fù)號代表根，數(shù)字代表該集合中元素個數(shù)
- 數(shù)組中如果為非負(fù)數(shù)，代表該元素雙親在數(shù)組中的下標(biāo)
所以在并查集中，我們會關(guān)注數(shù)組的下標(biāo)和數(shù)組的內(nèi)容。
如果數(shù)組的內(nèi)容是負(fù)數(shù)，那么他就是根（Root）
如果數(shù)組的內(nèi)容為（非負(fù)數(shù)），那么就指向他的父親。
所以我們能簡單解決這些問題
- 查找元素屬于哪個集合
沿著樹形關(guān)系一直往上尋找到根（直到找到內(nèi)容為負(fù)數(shù)的）
- 查看元素是否屬于同一個集合
尋找到根，不同則表示不是同一個集合
- 將兩個集合歸并成一個集合
一個集合歸并到另一個集合中，并修改集合的內(nèi)容
- 集合的個數(shù)
多少個負(fù)數(shù)內(nèi)容的位置，就有多少個集合
接下來，來簡單實現(xiàn)一個并查集
并查集的模擬
框架
//并查集
class UnionFindSet {
public:
//構(gòu)造函數(shù)
UnionFindSet(int n);
//查找元素所在的集合
int findRoot(int x);
//合并兩個元素所在的集合
void Union(int x1, int x2)
//獲取并查集中集合的個數(shù)
int SetCount();
private:
vector<int> _set;各個結(jié)點之間的關(guān)系
};
構(gòu)造
接收vector容器應(yīng)該預(yù)留的空間
初始化為-1
UnionFindSet(size_t size)
:_set(size,-1)
{}不需要自定析構(gòu)函數(shù)
默認(rèn)會調(diào)用系統(tǒng)默認(rèn)析構(gòu)
查找root
一直向上尋找，變換x ，直到找到內(nèi)容為負(fù)數(shù)
//查找元素是否在集合里
int FindRoot(int x)
{
while (_set[x] >= 0)
{
x = _set[x];
}
return x;
}合并倆個集合
將B合并到A中，A的根內(nèi)容要改變，B的根內(nèi)容也要改變
//合并
void Union(int x1, int x2)
{
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
if (root1 != root2)
{
_set[root1] += _set[root2];
_set[root2] = root1;
}
}路徑壓縮
如果有大量的數(shù)據(jù)，那么樹的層數(shù)可能非常高，查找的時候就需要一層一層往上迭代。這時候很浪費效率，這里就提出路徑壓縮。
路徑壓縮一般發(fā)送在查找根結(jié)點，會壓縮路徑上的所有結(jié)點，掛接到根上。
int FindRoot(int x)
{
//找根
int root = x;
while (_set[root ] >= 0)
{
root = _set[root ];
}
//壓縮
while (_set[x] >= 0)
{
int parent = _set[x];
_set[x] = root;
x = parent;
}
return root;
}Gitee:提取代碼
相關(guān)題目
LCR 116. 省份數(shù)量
思路：
運用并查集的相關(guān)知識
題目給我們一個相鄰矩陣，遍歷一半矩陣就能知道連通的關(guān)系。
我們把矩陣中為1的放到一個集合中，返回集合的數(shù)目文章來源：http://www.zghlxwxcb.cn/news/detail-827951.html
解題時，運用lambda表達(dá)式，調(diào)用找根root的函數(shù)。文章來源地址http://www.zghlxwxcb.cn/news/detail-827951.html
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n=isConnected[0].size();
vector<int> _ufs(n,-1);
//找根 >=0 就往上找
auto FindRoot=[&_ufs](int x)
{
int parent=x;
while(_ufs[parent]>=0)
{
parent=_ufs[parent];
}
return parent;
};
//遍歷，遇到1 并且根不同 就合并
for(int i=0;i<n;i++)
{
for(int j=0;j<=i;j++)
{
if(isConnected[i][j]==1)
{
int root1=FindRoot(i);
int root2=FindRoot(j);
if(root1!=root2)
{
_ufs[root1]+=_ufs[root2];
_ufs[root2]=root1;
}
}
}
}
int count =0;
for(auto x:_ufs)
{
if(x<0)
count++;
}
return count;
}
};到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】并查集的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
