資訊專欄INFORMATION COLUMN
摘要：并查集包括查詢和聯(lián)合，主要使用不相交集合查詢主要是用來決定不同的成員是否在一個(gè)子集合之內(nèi)聯(lián)合主要是用來把多個(gè)子集合成一個(gè)集合的實(shí)際運(yùn)用計(jì)算機(jī)網(wǎng)絡(luò)檢查集群是否聯(lián)通電路板檢查不同的電路元件是否聯(lián)通初始化聯(lián)通與檢測與是否聯(lián)通返回聯(lián)通的數(shù)
并查集(Union-Find)包括查詢(Find)和聯(lián)合(Union)，主要使用不相交集合(Disjoint-Sets)
查詢(Find)主要是用來決定不同的成員是否在一個(gè)子集合之內(nèi)
聯(lián)合(Union)主要是用來把多個(gè)子集合成一個(gè)集合
Union-Find的實(shí)際運(yùn)用：
1.計(jì)算機(jī)網(wǎng)絡(luò)檢查集群是否聯(lián)通 2.電路板檢查不同的電路元件是否聯(lián)通
Union-Find(mainly used for detection of connectivity problem):
Public Class UF:
UF(int n) //初始化(abstract N sites : list of integers to 0,1,2 .. N-1)
Void Union(int a, int b) //聯(lián)通a與b(add connection between a and b)
int find(int a) //component identifier
boolean isConnected(int a, int b) //檢測a與b是否聯(lián)通
int count() //返回聯(lián)通的數(shù)量(return number of connected components)
舉個(gè)例子：
Given Objects: 0, 1, 2, 3, 4, 5
union(0, 1):
0-1, 2, 3, 4, 5
union(1,3):
0-1-3, 2, 4, 5
union(2,5):
0-1-3, 2-5, 4
union(3, 5):
0-1-3-2-5, 4
Union-Find在計(jì)算機(jī)算法面試主要用來解決動態(tài)圖(Dynamic Graph)的一系列問題:
例如： 一個(gè)由0與1組成的二維矩陣，0可以看成海洋，1可以看成陸地
110101
001011
101011
100110
Q1:有多少島？4(dfs,bfs),靜態(tài)圖(static graph)
Q2:湖(上下左右不包換對角線被陸地包圍)的面積有多少? 2(dfs, bfs),靜態(tài)圖
Q3:如果改變圖中的元素有多少島?(0,0):5; (0,1):5; (0, 5): 6; (1,5): 5, 動態(tài)圖(Dynamic Graph)
Union-Find的種類：
Quick UnionFind(Quick-Union)
class QuickUnion:
private int[] ids;
public QuickUnionFind(int n):
ids = new int[n];
for(int i = 0; i < n; i++) {
ids[i] = i;
}
}
public void union(int a, int b) {
int idA = ids[a];
int idB = ids[b];
for(int i = 0; i < n; i++) {
if(ids[i] == idB){ //聯(lián)通所有與A聯(lián)通的元素
ids[i] = idA;
}
}
}
public boolean find(int a, int b) {
return ids[a] == ids[b];
}
}
比如，如果想要連通id[5]與id[9], 需要在union的過程中遍歷所有與id5連通的元素將下標(biāo)改成id9，或者將所有id9的下標(biāo)改成id5
QuickUnion的遍歷需要通過一次的數(shù)組讀取來找到對應(yīng)的節(jié)點(diǎn)，但是對于新增路徑需要需要線性時(shí)間找到對應(yīng)的組號進(jìn)行修改，所以對于大數(shù)據(jù)量來說如果新增路徑數(shù)量是M，節(jié)點(diǎn)的數(shù)量是N，我們需要O(MN)的時(shí)間復(fù)雜度來尋找對應(yīng)的標(biāo)號然后修改，平方的時(shí)間復(fù)雜度是非常費(fèi)時(shí)的，所以我們需要提高Union的效率
Tree Union Find
QuickUnion之所以Union的時(shí)間復(fù)雜度比較高主要是因?yàn)閷τ诿總€(gè)節(jié)點(diǎn)的所屬的組都是多帶帶記錄，因此需要一種更優(yōu)化的數(shù)據(jù)結(jié)構(gòu)來快速更新節(jié)點(diǎn)所屬的組，因此我們可以用一個(gè)parent node來連接所有的sub node形成樹來降低Union的時(shí)間
使用parent-link將子節(jié)點(diǎn)與根節(jié)點(diǎn)連接，id[a]的值就是父節(jié)點(diǎn)的序號，因此通過查找，總可以從一個(gè)子節(jié)點(diǎn)查找到根節(jié)點(diǎn)(id[a] == a)，因此在處理不同組的時(shí)候，我們只需要找到每個(gè)元素的根節(jié)點(diǎn)然后更新根節(jié)點(diǎn)的指向就可以了，就相當(dāng)于將其中一個(gè)根節(jié)點(diǎn)所代表的樹變成另外一個(gè)根節(jié)點(diǎn)的子樹
class TreeUnionFind:
private int[] ids;
public TreeUnionFind(int n) {
ids = new int[n];
for(int i = 0; i < n; i++) {
ids[i] = i;
}
}
public int root(int a) {
int root = a;
while(ids[root] != root) {
ids[root] = root;
}
}
public boolean find(int a, int b) {
return root(a) == root(b);
}
public void union(int a, int b) {
int rootA = ids[a];
int rootB = ids[b];
ids[rootA] = rootB;
}
}
但是樹這種數(shù)據(jù)結(jié)果經(jīng)常會根據(jù)輸入數(shù)據(jù)本身的性質(zhì)而變化，如果輸入數(shù)據(jù)是有序的相對應(yīng)的樹會變成一個(gè)單一鏈表因而不具備范性的運(yùn)用情況
Weighted Quick Union Find
根據(jù)Quick-Union Find:
public void union(int a, int b) {
int idA = ids[a];
int idB = ids[b];
for(int i = 0; i < n; i++) {
if(ids[i] == idB){
ids[i] = idA;
}
}
}
ids[i] = idA是一種hard code的習(xí)慣，因?yàn)閞andom assign一棵樹是另外一棵樹的子樹沒有考慮輸入數(shù)據(jù)的規(guī)模，如果輸入數(shù)據(jù)p與q， 如果p數(shù)據(jù)所在樹的規(guī)模比q數(shù)據(jù)所在樹的規(guī)模大得多，p與q新形成的樹不是平衡樹
因此，需要總是需要用小的size的樹與大的size的樹合并從而盡量達(dá)到樹的平衡
class WeightedQuickUnionFind{
private int[] ids;
private int[] sizes;
public WeightedQuickUnionFind(int n) {
ids = new int[n];
sizes = new int[n]; //在quickUnion的基礎(chǔ)上增加一個(gè)記錄size的變量
for(int i = 0; i < n; i++) {
ids[i] = i;
sizes[i] = 1;//初始化size的大小為1
}
}
public int root(int a, int b) {
int root = a;
while(ids[root] != root) {
root = ids[root];
}
return root;
}
public void union(int a, int b) {
int rootA = ids[a];
int rootB = ids[b];
if(sizes[rootA] > sizes[rootB]) { //判斷size的大小來更新root
ids[rootB] = rootA;
sizes[rootA] += sizes[rootB];
} else {
ids[rootA] = rootB;
sizes[rootB] += sizes[rootA];
}
}
}
通過weightedQuickUnion, 可以通過O(logn)的時(shí)間復(fù)雜度來分別Union和Find所需要的元素
Weighted QuickUnion With Path Compression
在Weighted QuickUnion的基礎(chǔ)上我們可以通過路徑壓縮(path compression)就是把所有的元素下標(biāo)直接連接到父節(jié)點(diǎn)來達(dá)到降低Union和Find時(shí)間復(fù)雜度的目的
class weightedQuickUnionWithPathCompression{
private int[] ids;
private int[] sizes;
public weightedQuickUnionWithPathCompression(int n) {
ids = new int[n];
sizes = new int[n];
for(int i = 0; i < n; i++) {
ids[i] = i;
sizes[i] = 1;
}
}
public int root(int a, int b) {
int root = a;
while(ids[root] != root) {
root = ids[root];
}
while(a != root) { //connect sub element directly to root
int temp = ids[a];
ids[a] = root;
a = temp;
}
return root;
}
public boolean find(int a, int b) {
return root(a) == root(b);
}
public boolean union(int a, int b) {
int rootA = ids[a];
int rootB = ids[b];
if(sizes[rootA] > sizes[rootB]) {
ids[rootB] = rootA;
sizes[rootA] += sizes[rootB];
} else {
ids[rootA] = ids[rootB];
sizes[rootB] += sizes[rootA];
}
}
}
由此，以上就是所有關(guān)于動態(tài)連接的UnionFind的介紹，下圖是不同思路并查集的算法時(shí)間復(fù)雜度對比：
Algorithm
Quick UnionFind: Construct: O(n); Find: O(1); Union:O(n)
Tree UnionFind: Construct: O(n); Find: O(tree height); Union:O(n)
Weighted QuickUnionFind:Construct: O(n); Find: O(logn); Union:O(logn)
Weighted QuickUnionFind with Path Compression: Construct: O(n); Find: amortizedO(1); Union:amortizedO(1)
leetcode里使用UnionFind的題主要有:Number of Islands(lc200), LongestConsecutiveSequence(lc128), SurroundedRegion(lc130)
Surrounded Region:
Given a 2D board containing "X" and "O" (the letter O), capture all regions surrounded by "X".A region is captured by flipping all "O"s into "X"s in that surrounded region.
For Example:
XXXX
XOOX
XXOX
XOXX
After should become:
XXXX
XXXX
XXXX
XOXX
class Solution{
public void solve(char[][] board) {
//sanity check
if(board == null || board.length == 0) return;
int row = board.length;
int col = board[0].length;
int dummy = row * col; //create a dummy node to represent list of nodes
UnionFind uf = new UnionFind(row * col + 1);
for(int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
if(board[i][j] == "O") {
if(i == 0 || i == row - 1 || j == 0 || j == col - 1) {
uf.union(node(i, j), dummy); //connect corner nodes
} else {
if(i > 0 && board[i-1][j] == "O") uf.union(node(i, j), node(i-1, j));
if(i > 0 && board[i+1][j] == "O") uf.union(node(i, j), node(i-1, j));
if(j > 0 && board[i][j-1] == "O") uf.union(node(i, j), node(i, j-1));
if(j > 0 && board[i][j+1] == "O") uf.union(node(i, j), node(i, j+1));
}
}
}
}
for(int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
if(uf.isConnected(board[i][j], dummy)) board[i][j] = "O";
else board[i][j] = "X";
}
}
}
public int node(int i, int j) {
return i * col + j;//convert 2d dimension to 1d
}
}
class UnionFind{
int[] parents;
public UnionFind(int[] n) {
parents = new int[n];
for(int i = 0; i < n; i++) {
parents[i] = i;
}
}
public void union(int i, int j) {
int rootA = find(i);
int rootB = find(j);
if(rootA != rootB) {
parents[rootA] = rootB;
}
}
public int find(int node) {
if(parents[node] == node) return node;
parents[node] = find(parents[node]);
return parents[node];
}
public boolean isConnected(int n1, int n2) {
return find(n1) == find(n2);
}
}
References:
1.https://algs4.cs.princeton.ed...
2.http://blog.csdn.net/dm_vince...
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/68283.html
摘要：題目要求提供一個(gè)二維數(shù)組表示一張地圖，其中代表陸地，代表海洋。這里使用一個(gè)新的二維數(shù)組來表示對應(yīng)地圖上的元素屬于哪個(gè)并查集。在合并的時(shí)候先進(jìn)行判斷，如果二者為已經(jīng)相連的陸地，則無需合并，否則將新的二維數(shù)組上的元素指向所在的并查集。 題目要求 Given a 2d grid map of 1s (land) and 0s (water), count the number of isla...
摘要：算法鏈接學(xué)習(xí)工具，，環(huán)境搭建在小伙伴的推薦下，這個(gè)學(xué)期開始上普林斯頓的算法課。一系列的整數(shù)對代表與相互連接，比如等，每一個(gè)整數(shù)代表了一個(gè)。我覺得這個(gè)可能也是并查集相關(guān)應(yīng)用。這學(xué)期繼續(xù)學(xué)習(xí)深入理解了就能明白了。 《算法》鏈接：1.5 Case Study: Union-Find學(xué)習(xí)工具：mac，java8，eclipse,coursera 環(huán)境搭建在小伙伴的推薦下，這個(gè)學(xué)期開始上普林斯頓...
摘要：這樣就將一個(gè)集合的節(jié)點(diǎn)歸屬到同一個(gè)集合號下了。最后如果并查集中只有一個(gè)集合，則說明可以構(gòu)建樹。 Graph Valid Tree Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check w...
摘要：聯(lián)合查找算法是并查集數(shù)據(jù)結(jié)構(gòu)一種應(yīng)用。并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，其保持著用于處理一些不相交集合的合并及查詢問題。的特征是刪除節(jié)點(diǎn)。目前就職于騰訊事業(yè)部，從事神經(jīng)機(jī)器翻譯工作。 5. TF - Graph模塊TF把神經(jīng)網(wǎng)絡(luò)模型表達(dá)成一張拓?fù)浣Y(jié)構(gòu)的Graph，Graph中的一個(gè)節(jié)點(diǎn)表示一種計(jì)算算子。Graph從輸入到輸出的Tensor數(shù)據(jù)流動完成了一個(gè)運(yùn)算過程，這是對類似概率圖、神經(jīng)網(wǎng)絡(luò)等連接...
摘要：只有一個(gè)連通分量還沒有環(huán)，就是樹，無根樹。無向圖邊的兩端是對稱的，無向圖講究連通這個(gè)概念，沒有方向，沒有拓?fù)洌芟窦希苑浅＿m合用并查集來解決。并查集寫法參考注意方法用找的老大哥，合并的是的老大哥。 Graph Valid Tree Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each...
閱讀 1058·2019-08-30 12:57
閱讀 2141·2019-08-30 11:11
閱讀 2183·2019-08-29 15:20
閱讀 1877·2019-08-29 14:12
閱讀 3280·2019-08-28 17:51
閱讀 2383·2019-08-26 13:23
閱讀 804·2019-08-26 10:34
閱讀 3866·2019-08-23 12:37
