1.并查集

1.1 簡(jiǎn)介

• 用于解決檢查兩個(gè)元素是否屬于一個(gè)集合；
• 合并兩個(gè)元素各自所在的集合；

即：

• isSameSet(A,B)：其中A屬于set1，B屬于set2，看set1和set2是否為同一個(gè)集合。
• unionSet(A,B)：將A所在的集合set1和B所在的集合set2全部合并在一起，組成一個(gè)大集合set。使得set1中的任何一個(gè)元素肯定和set2中的任何元素在同一個(gè)集合中。

注：并查集初始化時(shí)必須把所有元素給出。

實(shí)現(xiàn)上述兩個(gè)功能可以用任意結(jié)構(gòu)，比如：

• list：
  • 通過A得到set1，然后遍歷set1看有沒有B
  • 將兩個(gè)鏈表接起來
• set：
  • 看set1中是否有B，O(1)
  • 將set2中的數(shù)據(jù)重新哈希，然后放到set1中，這得遍歷。

向上指針指向自己說明是這個(gè)集合的代表節(jié)點(diǎn)；

將2節(jié)點(diǎn)掛在1節(jié)點(diǎn)的后面。

若要找2節(jié)點(diǎn)的代表節(jié)點(diǎn)，則順著2節(jié)點(diǎn)的向上指針往上找，找到一個(gè)節(jié)點(diǎn)的向上指針指向自己，此節(jié)點(diǎn)就是代表節(jié)點(diǎn)。

并查集是一棵多叉樹：

是否在同一個(gè)集合：A、B各自向上找自己的代表節(jié)點(diǎn)，看是否相同。

合并：節(jié)點(diǎn)少的掛在節(jié)點(diǎn)多的集合的代表節(jié)點(diǎn)下。

優(yōu)化：在查找4的代表節(jié)點(diǎn)時(shí)，找到1后，將4-1這條路徑經(jīng)過的節(jié)點(diǎn)變?yōu)楸馄降?#xff08;將圖左邊的結(jié)構(gòu)變?yōu)橛疫叺慕Y(jié)構(gòu)），都直接連在代表節(jié)點(diǎn)1上。4之后的節(jié)點(diǎn)先不管。

fatherMap：<child,father>，存的是節(jié)點(diǎn)和它的父親，依據(jù)這個(gè)表可以找到節(jié)點(diǎn)的所在集合的代表節(jié)點(diǎn)。

sizeMap：<node,Integer>，某一個(gè)節(jié)點(diǎn)它對(duì)應(yīng)的集合中的節(jié)點(diǎn)個(gè)數(shù)。

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

import java.util.HashMap; import java.util.List;public class UnionFind {public static class Node {// whatever you like}public static class UnionFindSet {public HashMap<Node, Node> fatherMap;//<child,father>public HashMap<Node, Integer> sizeMap;public UnionFindSet(List<Node> nodes) {makeSets(nodes)}private void makeSets(List<Node> nodes) {fatherMap = new HashMap<Node, Node>();sizeMap = new HashMap<Node, Integer>();for (Node node : nodes) {fatherMap.put(node, node);//鏈表中每個(gè)節(jié)點(diǎn)是一個(gè)獨(dú)立的集合，指向自己sizeMap.put(node, 1);//集合中的節(jié)點(diǎn)數(shù)為1}}private Node findHead(Node node) {//找某個(gè)節(jié)點(diǎn)所在集合的代表節(jié)點(diǎn)Node father = fatherMap.get(node);//遞歸if (father != node) {father = findHead(father);}fatherMap.put(node, father);//扁平化return father;}public boolean isSameSet(Node a, Node b) {return findHead(a) == findHead(b);}public void union(Node a, Node b) {if (a == null || b == null) {return;}Node aHead = findHead(a);Node bHead = findHead(b);if (aHead != bHead) {//不在一個(gè)集合中才需要合并int aSetSize= sizeMap.get(aHead);int bSetSize = sizeMap.get(bHead);if (aSetSize <= bSetSize) {//a中元素個(gè)數(shù)少，則將a的father指向bfatherMap.put(aHead, bHead);sizeMap.put(bHead, aSetSize + bSetSize);//只改了代表節(jié)點(diǎn)的size，其他節(jié)點(diǎn)的不用管//只有head的size是有用的信息，其他節(jié)點(diǎn)的size用不到} else {fatherMap.put(bHead, aHead);sizeMap.put(aHead, aSetSize + bSetSize);}}}} }

查兩個(gè)元素是否在一個(gè)集合，也可任意決定兩個(gè)集合是否合并。——只要兩個(gè)操作的總次數(shù)逼近O(N)及以上，那么平均下來，單次查詢和合并的時(shí)間復(fù)雜度為O(1)。

findHead()的詳細(xì)過程，假設(shè)當(dāng)前node為節(jié)點(diǎn)4：

最終結(jié)果：

findHead()的非遞歸實(shí)現(xiàn)：

public node findHead(Node node){Node cur=node;Node father=fatherMap.get(cur);Stack<Node> stack=new Stack<Node>();while(cur!=father){stack.put(cur);cur=father;father=fatherMap.get(father);}while(!stack.isEmpty()){fatherMap.put(stack.pop(),father);}return father; }

1.3 舉例

島問題

一個(gè)矩陣中只有0和1兩種值， 每個(gè)位置都可以和自己的上、 下、 左、 右四個(gè)位置相連， 如果有一片1連在一起， 這個(gè)部分叫做一個(gè)島， 求一個(gè)矩陣中有多少個(gè)島？

舉例：

0 0 1 0 1 0
1 1 1 0 1 0
1 0 0 1 0 0
0 0 0 0 0 0

這個(gè)矩陣中有三個(gè)島。

1.3.1 分析

這個(gè)問題原問題不用并查集結(jié)構(gòu)，可用遞歸結(jié)構(gòu)搞定。

但是若給定的矩陣特別大，需采用分治思想，多任務(wù)并行。

具體方法：

給定如下矩陣：

使用雙層for循環(huán)，遍歷每一個(gè)位置的元素，當(dāng)遍歷到某個(gè)位置時(shí)：

• 若此位置的元素為1時(shí)，將其相連的1都變?yōu)?，島數(shù)量加1——感染；
• 若為0，跳過；
• 若為2，也跳過.

上述矩陣，當(dāng)遍歷到(0,0)位置時(shí)，元素為1，則感染結(jié)果如下圖：

島數(shù)量由0變?yōu)?；

后面一直是2或0，直接跳過，直到位置(1,4)時(shí)，是1，則感染，島數(shù)量變?yōu)?：

再直到遍歷到最后一個(gè)位置的元素時(shí)，才是1，感染為2，島數(shù)量加一，變?yōu)?：

所以島數(shù)量為3.

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

package Hash;public class IslandCount {public static void main(String[] args) {int[][] m1 = { { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 0, 1, 1, 1, 0 }, { 0, 1, 1, 1, 0, 0, 0, 1, 0 },{ 0, 1, 1, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 1, 1, 0, 0 }, { 0, 0, 0, 0, 1, 1, 1, 0, 0 },{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };System.out.println(islandCount(m1));int[][] m2 = { { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 1, 1, 1, 1, 0 }, { 0, 1, 1, 1, 0, 0, 0, 1, 0 },{ 0, 1, 1, 0, 0, 0, 1, 1, 0 }, { 0, 0, 0, 0, 0, 1, 1, 0, 0 }, { 0, 0, 0, 0, 1, 1, 1, 0, 0 },{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };System.out.println(islandCount(m2));}public static int islandCount(int[][] arr) {int N=arr.length;int M=arr[0].length;int count=0;for(int i=0;i<N;i++) {for(int j=0;j<M;j++) {if(arr[i][j]==1) {count++;infect(arr,i,j,N,M);}}}return count;}public static void infect(int[][] arr,int i,int j, int N,int M) {if(i<0||i>N||j<0||j>M||arr[i][j]!=1)return;arr[i][j]=2;infect(arr,i+1,j,N,M);//右infect(arr,i,j+1,N,M);//下infect(arr,i-1,j,N,M);//左infect(arr,i,j-1,N,M);//上} }

運(yùn)行結(jié)果：

分割，讓多CPU運(yùn)行，然后用合適的合并邏輯進(jìn)行合并。

• 合并時(shí)需要處理邊界信息，如下圖：

左有3個(gè)島，右有2個(gè)島，但是合起來之后只有4個(gè)島。

確定每個(gè)感染點(diǎn)的感染中心，如下：

左邊矩陣中有A和B兩個(gè)感染中心。需要記錄的信息：

• 島的個(gè)數(shù)是兩個(gè)
• 邊界中4個(gè)1的感染中心分別是什么。
• 右邊矩陣的分析如下：

合并的時(shí)候：

• 先看這兩個(gè)1的感染中心點(diǎn)A和C是否在一個(gè)集合中，不在，說明沒有合并過，島的總個(gè)數(shù)-1，然后將A和C合在一起；
• 接著下一對(duì)，感染中心還是A，C，已經(jīng)在一個(gè)集合中了，不管；
• 下面是B和C，不在一個(gè)集合中，則島的總個(gè)數(shù)-1，將B和C放在一個(gè)集合中。

可將左右的邊界信息放在一個(gè)分布式內(nèi)存中，即在這個(gè)分布式內(nèi)存中維護(hù)一個(gè)并查集，這個(gè)可用spark做。

總結(jié)

以上是生活随笔為你收集整理的算法练习day12——190331（并查集）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。