這篇文章主要為大家展示了“編程語(yǔ)言中數(shù)據(jù)結(jié)構(gòu)與算法之并查集的示例分析”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“編程語(yǔ)言中數(shù)據(jù)結(jié)構(gòu)與算法之并查集的示例分析”這篇文章吧。

成都創(chuàng)新互聯(lián)-云計(jì)算及IDC服務(wù)提供商，涵蓋公有云、IDC機(jī)房租用、中國(guó)電信成都樞紐中心、等保安全、私有云建設(shè)等企業(yè)級(jí)互聯(lián)網(wǎng)基礎(chǔ)服務(wù)，歡迎咨詢：18982081108

認(rèn)識(shí)并查集

對(duì)于并查集(不相交集合)，很多人會(huì)感到很陌生，沒(méi)聽(tīng)過(guò)或者不是特別了解。實(shí)際上并查集是一種挺高效的數(shù)據(jù)結(jié)構(gòu)。實(shí)現(xiàn)簡(jiǎn)單，只是所有元素統(tǒng)一遵從一個(gè)規(guī)律所以讓辦事情的效率高效起來(lái)。

對(duì)于定意義，百科上這么定義的：

并查集，在一些有N個(gè)元素的集合應(yīng)用問(wèn)題中，我們通常是在開(kāi)始時(shí)讓每個(gè)元素構(gòu)成一個(gè)單元素的集合，然后按一定順序將屬于同一組的元素所在的集合合并，其間要反復(fù)查找一個(gè)元素在哪個(gè)集合中。其特點(diǎn)是看似并不復(fù)雜，但數(shù)據(jù)量極大，若用正常的數(shù)據(jù)結(jié)構(gòu)來(lái)描述的話，往往在空間上過(guò)大，計(jì)算機(jī)無(wú)法承受；即使在空間上勉強(qiáng)通過(guò)，運(yùn)行的時(shí)間復(fù)雜度也極高，根本就不可能在比賽規(guī)定的運(yùn)行時(shí)間（1～3秒）內(nèi)計(jì)算出試題需要的結(jié)果，只能用并查集來(lái)描述。

并查集是一種樹(shù)型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合（Disjoint Sets）的合并及查詢問(wèn)題。常常在使用中以森林來(lái)表示。

并查集解析基本思想初始化，一個(gè)森林每個(gè)都為獨(dú)立。通常用數(shù)組表示，每個(gè)值初始為-1。各自為根

join

(a,b) 操作。a,b兩個(gè)集合合并。注意這里的a，并不是a,b合并，而是a,b的集合合并。這就派生了一些情況：a，b如果是獨(dú)立的(沒(méi)有和其他合并)，那么直接a指向b(或者b指向a)，即data[a]=b;同時(shí)為了表示這個(gè)集合有多少個(gè)，原本-1的b再次-1.即data[b]=-2.表示以b為父親的節(jié)點(diǎn)有|-2|個(gè)。

a,b

如果有集合(可能有父親，可能自己是根)，那么我們當(dāng)然不能直接操作a,b(因?yàn)閍,b可能已經(jīng)指向別人了.)那么我們只能操作a,b的祖先。因?yàn)閍,b的祖先是沒(méi)有指向的(即數(shù)據(jù)為負(fù)值表示大小)。那么他們首先一個(gè)負(fù)值要加到另外一個(gè)上面去。另外這個(gè)數(shù)值要變成指向的那個(gè)表示聯(lián)系。

對(duì)于上述你可能會(huì)有疑問(wèn)：

如何查看a,b是否在一個(gè)集合？查看是否在一個(gè)集合，只需要查看節(jié)點(diǎn)根祖先的結(jié)果是否相同即可。因?yàn)橹挥?strong>根的數(shù)值是負(fù)的，而其他都是正數(shù)表示指向的元素。所以只需要一直尋找直到不為正數(shù)進(jìn)行比較即可！a,b合并，究竟是a的祖先合并在b的祖先上，還是b的祖先合并在a上？這里會(huì)遇到兩種情況，這個(gè)選擇也是非常重要的。你要弄明白一點(diǎn)：樹(shù)的高度+1的化那么整個(gè)元素查詢的效率都會(huì)降低！

所以我們通常是：小數(shù)指向大樹(shù)(或者低樹(shù)指向高樹(shù))，這個(gè)使得查詢效率能夠增加！

當(dāng)然，在高度和數(shù)量的選擇上，還需要你自己選擇和考慮。

其他路徑壓縮？

每次查詢，自下向上。當(dāng)我們調(diào)用遞歸的時(shí)候，可以順便壓縮路徑，因?yàn)槲覀儾檎乙粋€(gè)元素其實(shí)只需要直到它的祖先，所以當(dāng)他距離祖先近那么下次查詢就很快。并且壓縮路徑的代價(jià)并不大！

代碼實(shí)現(xiàn)

并查集實(shí)現(xiàn)起來(lái)較為簡(jiǎn)單，直接貼代碼！

package 并查集不想交集合;

import java.util.Scanner;
public class DisjointSet {
	static int tree[]=new int[100000];//假設(shè)有500個(gè)值
	public DisjointSet() 	{set(this.tree);}
	public DisjointSet(int tree[]) 
	{
		this.tree=tree;
		set(this.tree);
	}
	public void set(int a[])//初始化所有都是-1 有兩個(gè)好處，這樣他們指向-1說(shuō)明是自己，第二，-1代表當(dāng)前森林有-（-1）個(gè)
	{
		int l=a.length;
		for(int i=0;i<l;i++)
		{
			a[i]=-1;
		}
	}
	public int search(int a)//返回頭節(jié)點(diǎn)的數(shù)值
	{
		if(tree[a]>0)//說(shuō)明是子節(jié)點(diǎn)
		{
			return tree[a]=search(tree[a]);//路徑壓縮
		}
		else
			return a;
	}
	public int value(int a)//返回a所在樹(shù)的大?。▊€(gè)數(shù)）
	{
		if(tree[a]>0)
		{
			return value(tree[a]);
		}
		else
			return -tree[a];
	}
	public void union(int a,int b)//表示 a，b所在的樹(shù)合并
	{
		int a1=search(a);//a根
		int b1=search(b);//b根
		if(a1==b1) {System.out.println(a+"和"+b+"已經(jīng)在一棵樹(shù)上");}
		else {
		if(tree[a1]<tree[b1])//這個(gè)是負(fù)數(shù)，為了簡(jiǎn)單減少計(jì)算，不在調(diào)用value函數(shù)
		{
			tree[a1]+=tree[b1];//個(gè)數(shù)相加 注意是負(fù)數(shù)相加
			tree[b1]=a1;  //b樹(shù)成為a的子樹(shù)，直接指向a；
		}
		else
		{
			tree[b1]+=tree[a1];//個(gè)數(shù)相加 注意是負(fù)數(shù)相加
			tree[a1]=b1;  //b樹(shù)成為a的子樹(shù)，直接指向a；
		}
		}
	}
	public static void main(String[] args)
	{		
		DisjointSet d=new DisjointSet();
		d.union(1,2);
		d.union(3,4);
		d.union(5,6);
		d.union(1,6);
		
		d.union(22,24);
		d.union(3,26);
		d.union(36,24);
		System.out.println(d.search(6));	//頭
		System.out.println(d.value(6));  //大小
		System.out.println(d.search(22));	//頭
		System.out.println(d.value(22));  //大小
	}
}

package 并查集不想交集合;import java.util.Scanner;public class DisjointSet {static int tree[]=new int[100000];//假設(shè)有500個(gè)值public DisjointSet() {set(this.tree);}public DisjointSet(int tree[]) {this.tree=tree;set(this.tree);}public void set(int a[])//初始化所有都是-1 有兩個(gè)好處，這樣他們指向-1說(shuō)明是自己，第二，-1代表當(dāng)前森林有-（-1）個(gè){int l=a.length;for(int i=0;i<l;i++){a[i]=-1;}}public int search(int a)//返回頭節(jié)點(diǎn)的數(shù)值{if(tree[a]>0)//說(shuō)明是子節(jié)點(diǎn){return tree[a]=search(tree[a]);//路徑壓縮}elsereturn a;}public int value(int a)//返回a所在樹(shù)的大?。▊€(gè)數(shù)）{if(tree[a]>0){return value(tree[a]);}elsereturn -tree[a];}public void union(int a,int b)//表示 a，b所在的樹(shù)合并{int a1=search(a);//a根int b1=search(b);//b根if(a1==b1) {System.out.println(a+"和"+b+"已經(jīng)在一棵樹(shù)上");}else {if(tree[a1]<tree[b1])//這個(gè)是負(fù)數(shù)，為了簡(jiǎn)單減少計(jì)算，不在調(diào)用value函數(shù){tree[a1]+=tree[b1];//個(gè)數(shù)相加 注意是負(fù)數(shù)相加tree[b1]=a1; //b樹(shù)成為a的子樹(shù)，直接指向a；}else{tree[b1]+=tree[a1];//個(gè)數(shù)相加 注意是負(fù)數(shù)相加tree[a1]=b1; //b樹(shù)成為a的子樹(shù)，直接指向a；}}}public static void main(String[] args){DisjointSet d=new DisjointSet();d.union(1,2);d.union(3,4);d.union(5,6);d.union(1,6);d.union(22,24);d.union(3,26);d.union(36,24);System.out.println(d.search(6));//頭System.out.println(d.value(6)); //大小System.out.println(d.search(22));//頭System.out.println(d.value(22)); //大小}}

結(jié)語(yǔ)并查集屬于簡(jiǎn)單但是很高效率的數(shù)據(jù)結(jié)構(gòu)。在集合中經(jīng)常會(huì)遇到。如果不采用并查集而傳統(tǒng)暴力效率太低，而不被采納。另外，并查集還廣泛用于迷宮游戲中。

以上是“編程語(yǔ)言中數(shù)據(jù)結(jié)構(gòu)與算法之并查集的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

文章題目：編程語(yǔ)言中數(shù)據(jù)結(jié)構(gòu)與算法之并查集的示例分析
網(wǎng)頁(yè)鏈接：http://chinadenli.net/article20/pppsco.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站制作、域名注冊(cè)、網(wǎng)站內(nèi)鏈、電子商務(wù)、手機(jī)網(wǎng)站建設(shè)、定制開(kāi)發(fā)

廣告

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