C++實(shí)現(xiàn)并查集結(jié)構(gòu)-創(chuàng)新互聯(lián)

前言

并查集一般用于多元素，多集合的查找問題；
聽說很有用，但是平時(shí)好像確實(shí)沒有怎么見過。。
leetcode典型例題：島嶼數(shù)量

成都創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),新安企業(yè)網(wǎng)站建設(shè),新安品牌網(wǎng)站建設(shè),網(wǎng)站定制,新安網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,新安網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競爭力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。一、原理
  • 其實(shí)并查集的每個(gè)小集合就是一張有向圖，只不過是所有子節(jié)點(diǎn)指向父節(jié)點(diǎn)的圖結(jié)構(gòu)。
    在這里插入圖片描述
    他之所以能夠高效的合并和查找，是因?yàn)樗诓檎疫^程中，一直在動(dòng)態(tài)更改所有走過節(jié)點(diǎn)的父節(jié)點(diǎn)。
主要結(jié)構(gòu)：

這里先定義一個(gè)節(jié)點(diǎn)結(jié)構(gòu)：

templateclass EleNode
{public:
	T value;
	EleNode* father;
	EleNode(T val)
	{value = val;
		father = nullptr;
	}
};
  • 該節(jié)點(diǎn)結(jié)構(gòu)非常類似于鏈表
    只不過它里面存的指針指向自己的爸爸

主結(jié)構(gòu)中：

  • nodeMap根據(jù)用戶數(shù)據(jù)存儲(chǔ)對(duì)應(yīng)節(jié)點(diǎn)數(shù)據(jù)，所有被創(chuàng)建出來的節(jié)點(diǎn)都被存放在里面
  • numMap僅用于記錄該集合的元素?cái)?shù)量（只記錄頭部元素，因?yàn)檫@個(gè)數(shù)據(jù)只需要一條）
  • void createNode(T val)函數(shù)中，創(chuàng)建節(jié)點(diǎn)需要在nodeMap和numMap中初始化
templateclass UnionFindSet
{//節(jié)點(diǎn)記錄
	unordered_map*>nodeMap;
	//元素集數(shù)量記錄
	unordered_map*, int>numMap;
public:
	UnionFindSet(){}
	//構(gòu)造函數(shù)
	UnionFindSet(const vector& list)
	{for (int i = 0; i< list.size(); i++)
		{	createNode(list[i]);
		}
	}
	//銷毀節(jié)點(diǎn)
	~UnionFindSet()
	{for (auto ele : nodeMap)
		{	delete ele.second;
		}
	}

	// 新建一個(gè)節(jié)點(diǎn)
	void createNode(T val)
	{if (nodeMap.find(val) != nodeMap.end()) return;
		EleNode* newNode = new EleNode(val);
		nodeMap.insert(make_pair(val, newNode));
		numMap.insert(make_pair(newNode, 1));
	}
}
主要方法：

有三個(gè)方法，分別為：

// 判斷是否在同個(gè)集合中
bool isSameSet(const T& v1, const T& v2);
// 執(zhí)行聯(lián)合，即合并節(jié)點(diǎn)
void doUnion(EleNode* t1, EleNode* t2);
//找頭節(jié)點(diǎn)
EleNode* findHead(EleNode* node);
  1. 判斷是否在同個(gè)集合中
    判斷兩個(gè)節(jié)點(diǎn)的頭節(jié)點(diǎn)是不是同一個(gè)。
    為啥要找到頭節(jié)點(diǎn)？
    其實(shí)根據(jù)剛才的那張圖就很顯而易見
  • 如果兩個(gè)節(jié)點(diǎn)在同一個(gè)集合中，那么他們兩個(gè)一直執(zhí)行查找父親的操作；最后絕對(duì)能找到同一個(gè)頭節(jié)點(diǎn)
  • 如果兩個(gè)節(jié)點(diǎn)不在同集合中，那么執(zhí)行該操作過后；最后絕對(duì)找到不同的頭節(jié)點(diǎn)
// 是否為同個(gè)集合
	bool isSameSet(const T& v1, const T& v2)
	{assert(nodeMap.find(v1) != nodeMap.end() && nodeMap.find(v2) != nodeMap.end());
		return findHead(nodeMap[v1]) == findHead(nodeMap[v2]);
	}
  1. 合并節(jié)點(diǎn)
  • 將節(jié)點(diǎn)數(shù)量較小的那個(gè)集合，它的頭部節(jié)點(diǎn)的指針指向節(jié)點(diǎn)數(shù)量較大集合的頭節(jié)點(diǎn)。
    這實(shí)際上也是兩個(gè)圖結(jié)構(gòu)的合并。至于為啥要選出節(jié)點(diǎn)少的一邊，這個(gè)跟并查集的優(yōu)化邏輯有關(guān)，放在下面的方法說。

1>首先判斷他們是否已經(jīng)在同個(gè)集合中，在同集合中就跳出。
2>再分別找到他們兩個(gè)的集合數(shù)量中的較大值和較小值
3>將數(shù)量較小的一方并入數(shù)量較大的一方，通過將較小集合頭節(jié)點(diǎn)的father指向改為較大集合頭部
4>更新集合數(shù)量值
在這里插入圖片描述

  • 比如上圖中，用戶輸入2和4時(shí)，應(yīng)該怎么操作？
    實(shí)際上就是直接將1號(hào)指針指向3號(hào)。
    改完以后：
    在這里插入圖片描述
// 執(zhí)行聯(lián)合
	void doUnion(EleNode* t1, EleNode* t2)
	{// 判斷頭節(jié)點(diǎn)并保存
		EleNode* head1 = findHead(t1);
		EleNode* head2 = findHead(t2);
		if (head1 == head2) return;

		//找較大較小集合
		EleNode* big = numMap[head1] >= numMap[head2] ? head1 : head2;
		EleNode* small = numMap[head1] >= numMap[head2] ? head2 : head1;
		//改頭
		small->father = big;
		//數(shù)值更新
		numMap[big] = numMap[big] + numMap[small];
		numMap.erase(small);
	}
public:
	// 執(zhí)行聯(lián)合外部接口
	void doUnion(const T& v1, const T& v2)
	{assert(nodeMap.find(v1) != nodeMap.end() && nodeMap.find(v2) != nodeMap.end());
		doUnion(nodeMap[v1], nodeMap[v2]);
	}
  1. 找頭節(jié)點(diǎn)
  • 找頭節(jié)點(diǎn)的操作不僅僅是找到頭部，還包含了一個(gè)重要的優(yōu)化
  • 這個(gè)優(yōu)化就是將所有走過的，非頭節(jié)點(diǎn)全部直接連在頭結(jié)點(diǎn)上
  • 并查集中，一個(gè)集合(圖)最理想的狀態(tài)就是所有子節(jié)點(diǎn)全部直接指向頭節(jié)點(diǎn)，這種情況下，從子節(jié)點(diǎn)向上尋找頭節(jié)點(diǎn)的代價(jià)是O(1)

例：從2位置開始，找到集合頭部
在這里插入圖片描述
執(zhí)行后：
在這里插入圖片描述

  • 此時(shí)集合內(nèi)節(jié)點(diǎn)數(shù)量未改變不需要調(diào)整，只需要調(diào)整結(jié)構(gòu)即可

下面的函數(shù)中，將所有走過的路徑全部壓入棧內(nèi)，并在找到頭節(jié)點(diǎn)后，挨個(gè)將他的父親改為頭節(jié)點(diǎn)，最后返回頭部。

//找頭
	EleNode* findHead(EleNode* node)
	{stack*>path;
		while (node->father != nullptr)
		{	path.push(node);
			node = node->father;
		}
		while (!path.empty())
		{	path.top()->father = node;
			path.pop();
		}
		return node;
	}
二、全部代碼
#include#include#include#include#includeusing namespace std;

templateclass EleNode
{public:
	T value;
	EleNode* father;
	EleNode(T val)
	{value = val;
		father = nullptr;
	}
};

templateclass UnionFindSet
{//節(jié)點(diǎn)記錄
	unordered_map*>nodeMap;
	//元素集數(shù)量記錄
	unordered_map*, int>numMap;

	//找頭
	EleNode* findHead(EleNode* node)
	{stack*>path;
		while (node->father != nullptr)
		{	path.push(node);
			node = node->father;
		}
		while (!path.empty())
		{	path.top()->father = node;
			path.pop();
		}
		return node;
	}

	// 執(zhí)行聯(lián)合
	void doUnion(EleNode* t1, EleNode* t2)
	{EleNode* head1 = findHead(t1);
		EleNode* head2 = findHead(t2);
		if (head1 == head2) return;

		//合并
		EleNode* big = numMap[head1] >= numMap[head2] ? head1 : head2;
		EleNode* small = numMap[head1] >= numMap[head2] ? head2 : head1;
		small->father = big;
		numMap[big] = numMap[big] + numMap[small];
		numMap.erase(small);
	}
public:
	UnionFindSet(){}
	//構(gòu)造函數(shù)
	UnionFindSet(const vector& list)
	{for (int i = 0; i< list.size(); i++)
		{	createNode(list[i]);
		}
	}
	//銷毀節(jié)點(diǎn)
	~UnionFindSet()
	{for (auto ele : nodeMap)
		{	delete ele.second;
		}
	}

	// 新建一個(gè)節(jié)點(diǎn)
	void createNode(T val)
	{if (nodeMap.find(val) != nodeMap.end()) return;
		EleNode* newNode = new EleNode(val);
		nodeMap.insert(make_pair(val, newNode));
		numMap.insert(make_pair(newNode, 1));
	}

	// 判斷是否在同個(gè)集合中
	bool isSameSet(const T& v1, const T& v2)
	{assert(nodeMap.find(v1) != nodeMap.end() && nodeMap.find(v2) != nodeMap.end());
		return findHead(nodeMap[v1]) == findHead(nodeMap[v2]);
	}

	// 執(zhí)行聯(lián)合外部接口
	void doUnion(const T& v1, const T& v2)
	{assert(nodeMap.find(v1) != nodeMap.end() && nodeMap.find(v2) != nodeMap.end());
		doUnion(nodeMap[v1], nodeMap[v2]);
	}
};

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

新聞標(biāo)題：C++實(shí)現(xiàn)并查集結(jié)構(gòu)-創(chuàng)新互聯(lián)
文章URL：http://muchs.cn/article28/dcjicp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營銷推廣、外貿(mào)建站、網(wǎng)站設(shè)計(jì)公司、手機(jī)網(wǎng)站建設(shè)、品牌網(wǎng)站建設(shè)、域名注冊

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

h5響應(yīng)式網(wǎng)站建設(shè)