個人公眾號交流:bigsai

并查集(不相交集合)詳解與java實現

@

認識并查集

對于并查集(不相交集合),很多人會感到很陌生沒聽過或者不是特別了解。實際上并查集是一種挺高效的數據結構。實現簡單,只是所有元素統一遵從一個規律所以讓辦事情的效率高效起來。

對于定意義,百科上這么定義的:

并查集,在一些有N個元素的集合應用問題中,我們通常是在開始時讓每個元素構成一個單元素的集合,然后按一定順序將屬于同一組的元素所在的集合合并,其間要反復查找一個元素在哪個集合中。其特點是看似并不復雜,但數據量極大,若用正常的數據結構來描述的話,往往在空間上過大,計算機無法承受;即使在空間上勉強通過,運行的時間復雜度也極高,根本就不可能在比賽規定的運行時間(1~3秒)內計算出試題需要的結果,只能用并查集來描述。

并查集是一種樹型的數據結構,用于處理一些不相交集合(Disjoint Sets)的合并及查詢問題。常常在使用中以森林來表示。

并查集解析

基本思想

  • 初始化,一個森林每個都為獨立。通常用數組表示,每個值初始為-1。各自為根
    在這里插入圖片描述
  • join(a,b) 操作。a,b兩個集合合并。注意這里的a,并不是a,b合并,而是a,b的集合合并。這就派生了一些情況:
  • a,b如果是獨立的(沒有和其他合并),那么直接a指向b(或者b指向a),即data[a]=b;同時為了表示這個集合有多少個,原本-1的b再次-1.即data[b]=-2.表示以b為父親的節點有|-2|個。
    在這里插入圖片描述
    在這里插入圖片描述
  • a,b如果有集合(可能有父親,可能自己是根),那么我們當然不能直接操作a,b(因為a,b可能已經指向別人了.)那么我們只能操作a,b的祖先。因為a,b的祖先是沒有指向的(即數據為負值表示大小)。那么他們首先一個負值要加到另外一個上面去。另外這個數值要變成指向的那個表示聯系。
    在這里插入圖片描述

對于上述你可能會有疑問:

如何查看a,b是否在一個集合?

  • 查看是否在一個集合,只需要查看節點根祖先的結果是否相同即可。因為只有根的數值是負的,而其他都是正數表示指向的元素。所以只需要一直尋找直到不為正數進行比較即可

a,b合并,究竟是a的祖先合并在b的祖先上,還是b的祖先合并在a上?

  • 這里會遇到兩種情況,這個選擇也是非常重要的。你要弄明白一點:樹的高度+1的化那么整個元素查詢的效率都會降低!

所以我們通常是:小數指向大樹(或者低樹指向高樹),這個使得查詢效率能夠增加!
在這里插入圖片描述
當然,在高度和數量的選擇上,還需要你自己選擇和考慮。

其他路徑壓縮?

每次查詢,自下向上。當我們調用遞歸的時候,可以順便壓縮路徑,因為我們查找一個元素其實只需要直到它的祖先,所以當他距離祖先近那么下次查詢就很快。并且壓縮路徑的代價并不大!
在這里插入圖片描述

代碼實現

并查集實現起來較為簡單,直接貼代碼!

package 并查集不想交集合;

import java.util.Scanner;
public class DisjointSet {
	static int tree[]=new int[100000];//假設有500個值
	public DisjointSet() 	{set(this.tree);}
	public DisjointSet(int tree[]) 
	{
		this.tree=tree;
		set(this.tree);
	}
	public void set(int a[])//初始化所有都是-1 有兩個好處,這樣他們指向-1說明是自己,第二,-1代表當前森林有-(-1)個
	{
		int l=a.length;
		for(int i=0;i<l;i++)
		{
			a[i]=-1;
		}
	}
	public int search(int a)//返回頭節點的數值
	{
		if(tree[a]>0)//說明是子節點
		{
			return tree[a]=search(tree[a]);//路徑壓縮
		}
		else
			return a;
	}
	public int value(int a)//返回a所在樹的大小(個數)
	{
		if(tree[a]>0)
		{
			return value(tree[a]);
		}
		else
			return -tree[a];
	}
	public void union(int a,int b)//表示 a,b所在的樹合并
	{
		int a1=search(a);//a根
		int b1=search(b);//b根
		if(a1==b1) {System.out.println(a+"和"+b+"已經在一棵樹上");}
		else {
		if(tree[a1]<tree[b1])//這個是負數,為了簡單減少計算,不在調用value函數
		{
			tree[a1]+=tree[b1];//個數相加  注意是負數相加
			tree[b1]=a1;       //b樹成為a的子樹,直接指向a;
		}
		else
		{
			tree[b1]+=tree[a1];//個數相加  注意是負數相加
			tree[a1]=b1;       //b樹成為a的子樹,直接指向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));     //大小
	}
}

在這里插入圖片描述

結語

  • 并查集屬于簡單但是很高效率的數據結構。在集合中經常會遇到。如果不采用并查集而傳統暴力效率太低,而不被采納。
  • 另外,并查集還廣泛用于迷宮游戲中,下面有機會可以介紹用并查集實現一個走迷宮小游戲。大家歡迎關注!
  • 最后,歡迎大家關注筆者公眾號,一起學習、交流!筆者學習資源也放置公眾號和大家一起分享!

posted @ 2019-08-28 12:42  bigsai  閱讀(...)  評論(...編輯  收藏
個人公眾號交流:bigsai
丛林巫师APP下载
上证指数行情新浪财经 老快3基本走势图带连线 棒球比分几比几声 海王捕鱼上分技巧 黔友贵州麻将下载 湖北十一选五一定牛走势分布图 电竞比分网1zplay手机 新城股票 河南十一选五奖金分配 股票指数的作用 闲来麻将源码 浙江6+1开 福建快3一定牛推荐灭神 河南体彩快赢481开奖查询 天津十一选五计划软件 十一选五开奖结果山