并查集與最小生成樹(shù)
Java高階數(shù)據(jù)結(jié)構(gòu) & 并查集 & 最小生成樹(shù)
1. 并查集
1.1 并查集的原理
在一些應(yīng)用問(wèn)題中，我們常常會(huì)遇到一類(lèi)問(wèn)題
一開(kāi)始是一個(gè)人
- 后來(lái)新增的人可能與這個(gè)人有關(guān)系，也可能與這個(gè)人無(wú)關(guān)系。
- 一個(gè)人與一個(gè)人有關(guān)系，這個(gè)人與另一個(gè)人也有關(guān)系，那么三人都有關(guān)系。
- 有關(guān)系的和沒(méi)關(guān)系的之間是不同的類(lèi)別。
- 而隨著人數(shù)增加，有多少類(lèi)別是不確定的，所以用普通的二維數(shù)組是很難描述和存儲(chǔ)這種數(shù)據(jù)結(jié)構(gòu)的。
- 因?yàn)榧词乖诓豢紤]時(shí)間復(fù)雜度的情況下，我們不知道有多少行，并且出現(xiàn)“三人都有關(guān)系”的情況的時(shí)候，需要合并等等…
而現(xiàn)在有一種數(shù)據(jù)結(jié)構(gòu)，就專門(mén)去解決這個(gè)問(wèn)題，這就是 “并查集”
需要將n個(gè)不同的元素劃分成一些不相交的集合。
開(kāi)始時(shí)，每個(gè)元素自成一個(gè)單元素集合，然后按一定的規(guī)律將歸于同一組元素的集合合并。
在此過(guò)程中要反復(fù)用到查詢某一個(gè)元素歸屬于那個(gè)集合的運(yùn)算。適合于描述這類(lèi)問(wèn)題的抽象數(shù)據(jù)類(lèi)型稱為并查集(union-find set)
（先說(shuō)怎么存儲(chǔ)表示的，再說(shuō)如何構(gòu)建）
并查集是一個(gè)int型的一維數(shù)組，而本質(zhì)就是一維順序表存儲(chǔ)的“森林”
有如下特性：
- 每個(gè)節(jié)點(diǎn)都有對(duì)應(yīng)的下標(biāo)，如果有n個(gè)節(jié)點(diǎn)，那么他們就對(duì)應(yīng)數(shù)組的0-n-1
- 森林的不同的樹(shù)，代表不同的類(lèi)別
- 每棵樹(shù)都有一個(gè)根節(jié)點(diǎn)，這個(gè)根節(jié)點(diǎn)在數(shù)組中的值為負(fù)數(shù)，絕對(duì)值為這棵樹(shù)節(jié)點(diǎn)的個(gè)數(shù)
- 每棵樹(shù)的非根節(jié)點(diǎn)在數(shù)組中的值為其父節(jié)點(diǎn)在數(shù)組中的下標(biāo)
1.1.1 例子：
- 現(xiàn)在有十個(gè)人，他們分別代表0 - 9
- 他們?cè)净ゲ幌嘧R(shí)，但是今天是他們因?yàn)榫壏殖霈F(xiàn)在同一輛公交車(chē)上，這次行程他們都很長(zhǎng)，并且在路上網(wǎng)絡(luò)全無(wú)，他們也毫無(wú)困意，并且都是社牛。
- 他們開(kāi)始與周?chē)能?chē)友交談，可能因?yàn)楦鞣N原因，如興趣愛(ài)好和地域性，他們互相交換了微信。如果兩個(gè)人同時(shí)與一個(gè)人交換微信，那么這兩個(gè)人也會(huì)獲得對(duì)方的微信。
- 最終下電梯，他們的朋友圈是這樣的：
而并查集將變成這樣：
1.1.2 這樣存儲(chǔ)有什么好處呢？
如果有n個(gè)節(jié)點(diǎn)，那么一開(kāi)始分為n個(gè)類(lèi)別
如果a0與a1有關(guān)系，那么只需要讓a0和a1其中一棵樹(shù)根節(jié)點(diǎn)接到另一棵樹(shù)的根節(jié)點(diǎn)即可
- 一棵樹(shù)的根節(jié)點(diǎn)的值對(duì)于新的樹(shù)的節(jié)點(diǎn)數(shù)的負(fù)數(shù)
- 另一棵樹(shù)的根節(jié)點(diǎn)變?yōu)椤靶聵?shù)的非根節(jié)點(diǎn)”，其值為根節(jié)點(diǎn)的下標(biāo)
通過(guò)這個(gè)機(jī)制，最終會(huì)很好的分好類(lèi)別，不需要分好組讓把他們放進(jìn)去，而是他們自己分好了
- 因?yàn)橥豢脴?shù)的根節(jié)點(diǎn)都一樣，所以負(fù)數(shù)值的元素有多少個(gè)，就說(shuō)明有多少組
- 當(dāng)然所有非根節(jié)點(diǎn)都可以壓縮其值為其所在數(shù)的根節(jié)點(diǎn)對(duì)應(yīng)下標(biāo)
而判斷兩個(gè)節(jié)點(diǎn)有沒(méi)有關(guān)系，就只需要判斷他們根節(jié)點(diǎn)是否相同即可
1.2 并查集的代碼實(shí)現(xiàn)
了解完機(jī)制之后，并查集的代碼實(shí)現(xiàn)并不復(fù)雜！
1.2.1 類(lèi)的定義與屬性
public class UnionFindSet {
private int[] elem;
}
這就是并查集的主體
1.2.2 構(gòu)造方法
public UnionFindSet(int n) {
this.elem = new int[n];
Arrays.fill(this.elem, -1);
}
- 根據(jù)n構(gòu)造數(shù)組，并且利用fill充滿數(shù)組為-1
1.2.3 獲取下標(biāo)的方法
//根據(jù)需求得到下標(biāo)
public int getIndexByX(int x) {
return x;
}
- 這個(gè)需要根據(jù)實(shí)際需求
- 一般x與i是一致的
- 或者是x = ki + b（k屬于整數(shù)）
- 對(duì)于其他特殊情況，你需要給每個(gè)節(jié)點(diǎn)安排下標(biāo)
- 這一點(diǎn)只需要在傳參的時(shí)候轉(zhuǎn)化為下標(biāo)即可
下面的代碼都是認(rèn)為傳參的就是下標(biāo)
1.2.4 獲得根節(jié)點(diǎn)
public int findRoot(int x) {
if(x < 0) {
throw new IndexOutOfBoundsException("下標(biāo)為負(fù)數(shù)");
}
while(elem[x] >= 0) {
x = elem[x];
}
return x;
}
- 如果是壓縮后的并查集,直接返回elem[x]即可
- 如果不是，這需要溯源到根節(jié)點(diǎn)
1.2.5 兩個(gè)節(jié)點(diǎn)建立聯(lián)系
- 只要兩個(gè)節(jié)點(diǎn)來(lái)自不同的樹(shù)，那么就可以建立聯(lián)系，即兩個(gè)集合合并
- 如果來(lái)自同一棵樹(shù)，什么也不做
注意：這里你可以選擇x1合并x2，或者x2合并x1
//合并x1和x2
//設(shè)x1任然是根節(jié)點(diǎn)，x2連接到x1下
public void union(int x1, int x2) {
int index1 = findRoot(x1);
int index2 = findRoot(x2);
if(index1 == index2) {
return;//同一棵樹(shù)
}else {
elem[index1] += elem[index2];
elem[index2] = index1;
}
}
例子：
1.2.6 判斷兩個(gè)節(jié)點(diǎn)是否在一個(gè)集合內(nèi)
//判斷是否在一個(gè)集合內(nèi)
public boolean isSameSet(int x1, int x2) {
return findRoot(x1) == findRoot(x2);
}
1.2.7 計(jì)算集合的個(gè)數(shù)
//計(jì)算集合的個(gè)數(shù)
public int getSetCount() {
int count = 0;
for(int x : elem) {
if(x < 0) {
count++;
}
}
return count;
}
1.2.8 打印并查集
public void display() {
for(int x : elem) {
System.out.print(x + " ");
}
System.out.println();
}
1.3 并查集的應(yīng)用
1.3.1 省份的數(shù)量
力扣547
是不是一模一樣，^ v ^
分析：
代碼：
//獲得省份數(shù)量
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
UnionFindSet unionFindSet = new UnionFindSet(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if(isConnected[i][j] == 1) {
unionFindSet.union(i, j);
}
}
}
return unionFindSet.getSetCount();
}
1.3.2 等式方程的可滿足性
力扣990
分析：
思路：
- 區(qū)分不同的字符串種類(lèi)（等于號(hào)類(lèi)和不等號(hào)類(lèi)）
- 通過(guò)等號(hào)類(lèi)構(gòu)建并查集
- 通過(guò)不等號(hào)類(lèi)去檢查是否合理
//下標(biāo)轉(zhuǎn)化方法（這道題節(jié)點(diǎn)最多26個(gè)，因?yàn)橹荒苁遣恢貜?fù)的小寫(xiě)字母）
public int getIndexByX(char x) {
return x - 'a';
}
//等式方程可滿足性
public boolean equationsPossible(String[] equations) {
UnionFindSet unionFindSet = new UnionFindSet(26);
for(String str : equations) {
if(str.charAt(1) == '=') {
char ch1 = str.charAt(0);
char ch2 = str.charAt(3);
unionFindSet.union(getIndexByX(ch1), getIndexByX(ch2));
}
}
for(String str : equations) {
if(str.charAt(1) == '!') {
char ch1 = str.charAt(0);
char ch2 = str.charAt(3);
if(unionFindSet.isSameSet(getIndexByX(ch1), getIndexByX(ch2))) {
return false;
}
}
}
return true;
}
1.3.3 Kruskal算法獲取圖的最小生成樹(shù)
這也是接下來(lái)要講的
2. 圖的最小生成樹(shù)問(wèn)題
對(duì)于圖的基本知識(shí)，請(qǐng)參考博客：Java高階數(shù)據(jù)結(jié)構(gòu) & 圖 & 圖的表示與遍歷_s:103的博客-CSDN博客
下面不作贅述~
2.1 生成樹(shù)是什么
連通圖中的每一棵生成樹(shù)，都是原圖的一個(gè)極大無(wú)環(huán)子圖，即：從其中刪去任何一條邊，生成樹(shù) 就不在連 通；反之，在其中引入任何一條新邊，都會(huì)形成一條回路。
若連通圖由n個(gè)頂點(diǎn)組成，則其生成樹(shù)必含n個(gè)頂點(diǎn)和n-1條邊。因此構(gòu)造最小生成樹(shù)的準(zhǔn)則有五 條：
- 只能由圖中的邊來(lái)構(gòu)造最小生成樹(shù)
- 只能使用恰好n-1條邊來(lái)連接圖中的n個(gè)頂點(diǎn)
- 選用的n-1條邊不能構(gòu)成回路
- 當(dāng)然，都滿足第2條，就一定不會(huì)構(gòu)成回路
- n-1條邊的權(quán)和最小
- 是連通圖
- 只有連通無(wú)向圖存在生成樹(shù)
當(dāng)然，最小生成樹(shù)，可能不止一棵
2.2 獲取最小生成樹(shù)算法
貪心算法： 是指在問(wèn)題求解時(shí)，總是做出當(dāng)前看起來(lái)最好的選擇。也就是說(shuō)貪心算法做出的不是整體 最優(yōu)的 的選擇，而是某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有的問(wèn)題都能得到整體最優(yōu)解。
以下兩種算法的本質(zhì)都是貪心算法，雖然數(shù)學(xué)上不嚴(yán)謹(jǐn)，卻能很好的解決這個(gè)問(wèn)題~
- 不需要糾結(jié)，用就是了
2.2.1 Kruskal算法
- 克魯斯卡爾算法是全局的貪心算法
步驟：
- 選取全局中最短的邊，并標(biāo)記兩個(gè)頂點(diǎn)
-
選取全局中未被標(biāo)記的邊（兩個(gè)端點(diǎn)都未被標(biāo)記）
- 如果幾個(gè)一樣小的，沒(méi)關(guān)系，用哪個(gè)都o(jì)k
- 這也是為什么最小生成樹(shù)可能不唯一的原因
- 以此類(lèi)推…
- 在標(biāo)價(jià)前要判斷標(biāo)記后是否成環(huán)，如果是，取消此次選擇
- 直到選出n-1條邊，此時(shí)計(jì)算結(jié)束
例子：
- 求一棵如下圖的最小生成樹(shù)
步驟如下：
2.2.2 Prime算法
- 普利姆算法的本質(zhì)是局部的貪心算法
步驟：
- 確定并標(biāo)記一個(gè)起始節(jié)點(diǎn)，后續(xù)樹(shù)的生長(zhǎng)以此為基礎(chǔ)
- 生長(zhǎng)：在此節(jié)點(diǎn)能直接連通的所有節(jié)點(diǎn)中，選擇一條權(quán)最小的邊，并標(biāo)記該節(jié)點(diǎn)
-
繼續(xù)生長(zhǎng)：在樹(shù)的所有節(jié)點(diǎn)能直接連通的所有節(jié)點(diǎn)中，選擇一條權(quán)最小的邊，并標(biāo)記該節(jié)點(diǎn)
- 不能連通被標(biāo)記的節(jié)點(diǎn)
- 無(wú)向連通圖不會(huì)出現(xiàn)選不出來(lái)的情況
-
直到所有節(jié)點(diǎn)都被標(biāo)記則結(jié)束，已生長(zhǎng)成最小生成樹(shù)
- 或者是獲得了n-1條邊，不成環(huán)則一定有n個(gè)節(jié)點(diǎn)
例子：
- 求一棵如下圖以a的起始節(jié)點(diǎn)的最小生成樹(shù)
步驟：
可見(jiàn)，不同算法求出來(lái)的最小生成樹(shù)不同
2.3 獲取最小生成樹(shù)代碼實(shí)現(xiàn)
通過(guò)剛才的算法講解，其實(shí)思路不難，現(xiàn)在要解決的主要是算法轉(zhuǎn)化為代碼~
2.3.1 Kruskal算法代碼實(shí)現(xiàn)（鄰接矩陣）
待處理的問(wèn)題：
- 怎么獲得全場(chǎng)最短的邊？
- 怎么保證不會(huì)成環(huán)
解決：
-
優(yōu)先級(jí)隊(duì)列 去存儲(chǔ)所有的邊，每次都取小根堆堆頂，這樣可以高效的獲取最小邊
- 由于是全局的，所以不存在 “局部最小問(wèn)題”
- 并查集 去整理節(jié)點(diǎn)之間的關(guān)系，如果一條邊的兩個(gè)節(jié)點(diǎn)是有關(guān)系（已在同一個(gè)圖）的，就不能取
代碼實(shí)現(xiàn)：
- Edge類(lèi)的定義
static class Edge {
int src;
int dest;
int weight;
public Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
}
- 導(dǎo)入并查集這個(gè)類(lèi)（剛才實(shí)現(xiàn)的）
- 技巧：把代碼復(fù)制直接粘貼就行了
- 這樣會(huì)自動(dòng)根據(jù)public類(lèi)構(gòu)建java文件
- 庫(kù)魯斯卡爾算法對(duì)應(yīng)方法
/**
*
* @param minTree 最小生成樹(shù)放在圖 minTree中
* @return 最小生成樹(shù)的權(quán)和
*/
public int kruskal(GraphByMatrix minTree) {
//1. 優(yōu)先級(jí)序列存放所有邊
PriorityQueue<Edge> minHeap = new PriorityQueue<Edge>(
(o1, o2) -> {
return o1.weight - o2.weight;
}
);
int n = matrix.length;
//無(wú)向圖只需要一條即可
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
minHeap.offer(new Edge(i, j, matrix[i][j]));
}
}
//最終的權(quán)值和
int retWeight = 0;
//定義并查集
UnionFindSet unionFindSet = new UnionFindSet(n);
int size = 0;//已選邊的條數(shù)
//選取n-1條邊，如果不成環(huán)，必然選中n個(gè)節(jié)點(diǎn)，
// 如果隊(duì)列都空了，都沒(méi)有n-1條邊，則不是無(wú)向連通圖
while(size < n - 1 && !minHeap.isEmpty()) {
Edge minEdge = minHeap.poll();
int src = minEdge.src;
int dest = minEdge.dest;
//如果src與dest師出同門(mén)，不能添加
if(!unionFindSet.isSameSet(src, dest)) {
System.out.println(arrayV[src] +"--- "
+arrayV[dest]+" : "+matrix[src][dest]);
//這兩個(gè)節(jié)點(diǎn)建立關(guān)系
unionFindSet.union(src, dest);
//存放在minTree圖中，最小生成樹(shù)返回到這里面
minTree.addEdge(arrayV[src], arrayV[dest], minEdge.weight);
//權(quán)值和
retWeight += minEdge.weight;
//被選中的邊的條數(shù)加一
size++;
}
}
return size == n - 1 ? retWeight : Integer.MAX_VALUE;
}
測(cè)試：
- 建立圖對(duì)象（跟上面的圖解一致）
- 打印最小生成樹(shù)權(quán)和以及最小生成樹(shù)的鄰接矩陣
public static void testGraphMinTree1() {
String str = "abcdefghi";
char[] array =str.toCharArray();
GraphByMatrix g = new GraphByMatrix(str.length(),false);
g.initArrayV(array);
g.addEdge('a', 'b', 4);
g.addEdge('a', 'h', 8);
//g.addEdge('a', 'h', 9);
g.addEdge('b', 'c', 8);
g.addEdge('b', 'h', 11);
g.addEdge('c', 'i', 2);
g.addEdge('c', 'f', 4);
g.addEdge('c', 'd', 7);
g.addEdge('d', 'f', 14);
g.addEdge('d', 'e', 9);
g.addEdge('e', 'f', 10);
g.addEdge('f', 'g', 2);
g.addEdge('g', 'h', 1);
g.addEdge('g', 'i', 6);
g.addEdge('h', 'i', 7);
GraphByMatrix kminTree = new GraphByMatrix(str.length(),false);
kminTree.initArrayV(array);
System.out.println(g.kruskal(kminTree));
kminTree.printGraph();
}
public static void main(String[] args) {
testGraphMinTree1();
}
2.3.2 Prime算法代碼實(shí)現(xiàn)（鄰接矩陣）
待處理問(wèn)題：
- 怎么找到一條當(dāng)前標(biāo)記節(jié)點(diǎn)指向未標(biāo)記節(jié)點(diǎn)的邊
- 這條邊怎么保證是最小的
解決：
-
由于這種算法明顯分為了兩種關(guān)系：被標(biāo)記與未被標(biāo)記
- 所以直接創(chuàng)建兩個(gè)集合（HashSet）即可，不需要用到并查集
- 如果指向的頂點(diǎn)屬于被標(biāo)記過(guò)，則不能選擇它
- 選擇后目的頂點(diǎn)被標(biāo)記，也讓這條邊不會(huì)再次被選中
-
一樣可以用 優(yōu)先級(jí)隊(duì)列
-
每次一個(gè)頂點(diǎn)被標(biāo)記的時(shí)候，都需要將這個(gè)頂點(diǎn)連接的所有邊加入隊(duì)列中
-
重復(fù)的有很多，但是由于剛才的機(jī)制，不會(huì)出現(xiàn)成環(huán)的現(xiàn)象
-
在這里隊(duì)列是需要?jiǎng)討B(tài)更新的，每次都為了找到“局部最小”
-
代碼實(shí)現(xiàn)：
- 普利姆算法對(duì)應(yīng)方法
public int prime(GraphByMatrix minTree, char V) {
//獲取頂點(diǎn)的下標(biāo)
int srcIndex = getIndexOfV(V);
//起始節(jié)點(diǎn)集合與目的節(jié)點(diǎn)集合
Set<Integer> srcSet = new HashSet<>();
Set<Integer> destSet = new HashSet<>();
//初始化兩個(gè)集合
srcSet.add(srcIndex);
int n = matrix.length;
for (int i = 0; i < n; i++) {
if(i != srcIndex) {
destSet.add(i);
}
}
//從srcSet到destSet集合的邊
//定義優(yōu)先級(jí)隊(duì)列與初始化優(yōu)先級(jí)隊(duì)列
PriorityQueue<Edge> minHeap = new PriorityQueue<>(
(o1, o2) -> {
return o1.weight - o2.weight;
//左大于右為正，為升序小根堆
}
);
for (int i = 0; i < n; i++) {
if(matrix[srcIndex][i] != Integer.MAX_VALUE) {
minHeap.offer(new Edge(srcIndex, i, matrix[srcIndex][i]));
}
}
int retWeight = 0;//返回的權(quán)值和
int edgeCount = 0;//已選中的邊
//核心循環(huán)
while(edgeCount < n - 1 && !minHeap.isEmpty()) {
Edge minEdge = minHeap.poll();
int src = minEdge.src;
int dest = minEdge.dest;
//判斷dest是否被標(biāo)記
if(!srcSet.contains(dest)) {
minTree.addEdge(arrayV[src], arrayV[dest], matrix[src][dest]);
System.out.println(arrayV[src] + "---" + arrayV[dest] + " : "
+ matrix[src][dest]);
edgeCount++;
retWeight += matrix[src][dest];
//目的節(jié)點(diǎn)被標(biāo)記：加入srcSet，在destSet除名
srcSet.add(dest);
destSet.remove(dest);
//添加新增起始頂點(diǎn)的所有直接連通的邊
for (int i = 0; i < n; i++) {
//多重保證，安心！
if(matrix[dest][i] != Integer.MAX_VALUE && destSet.contains(i)) {
minHeap.offer(new Edge(dest, i, matrix[dest][i]));
}
}
}
}
return edgeCount == n - 1 ? retWeight : Integer.MAX_VALUE;
}
測(cè)試：
- 同上，只是把方法換成prime，并給定起始頂點(diǎn)
public static void testGraphMinTree2() {
String str = "abcdefghi";
char[] array =str.toCharArray();
GraphByMatrix g = new GraphByMatrix(str.length(),false);
g.initArrayV(array);
g.addEdge('a', 'b', 4);
g.addEdge('a', 'h', 8);
//g.addEdge('a', 'h', 9);
g.addEdge('b', 'c', 8);
g.addEdge('b', 'h', 11);
g.addEdge('c', 'i', 2);
g.addEdge('c', 'f', 4);
g.addEdge('c', 'd', 7);
g.addEdge('d', 'f', 14);
g.addEdge('d', 'e', 9);
g.addEdge('e', 'f', 10);
g.addEdge('f', 'g', 2);
g.addEdge('g', 'h', 1);
g.addEdge('g', 'i', 6);
g.addEdge('h', 'i', 7);
GraphByMatrix kminTree = new GraphByMatrix(str.length(),false);
kminTree.initArrayV(array);
System.out.println(g.prime(kminTree, 'a'));
kminTree.printGraph();
}
public static void main(String[] args) {
testGraphMinTree2();
}
這兩個(gè)算法的代碼可能比較難理解，你可以結(jié)合上面的圖片和文字講解去理解代碼！
文章到此結(jié)束！謝謝觀看
可以叫我 小馬，我可能寫(xiě)的不好或者有錯(cuò)誤，但是一起加油鴨??！文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-436892.html后續(xù)更新圖的最短路徑問(wèn)題和拓?fù)渑判?，敬?qǐng)期待！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-436892.html
到了這里，關(guān)于Java高階數(shù)據(jù)結(jié)構(gòu) & 并查集 & 最小生成樹(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
