本文實例為大家分享了Java實現并查集的具體代碼，供大家參考，具體內容如下
自下而上的樹結構
接口
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
/** * @author Nino */public interface UF { int size(); /** * 看兩個元素是否相連 * @param p * @param q * @return */ boolean isConnected(int p, int q); /** * 將兩個元素合并在一起，變成一個集合中的元素 * @param p * @param q */ void unionElements(int p, int q);} |
使用路徑壓縮的并查集
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
/** * @author Nino */public class UnionFind5 implements UF { private int[] parent; //rank[i]表示以i為根的集合中樹的層數 private int[] rank; public UnionFind5(int size) { parent = new int[size]; rank = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; rank[i] = 1; } } @Override public int size() { return parent.length; } /** * 查找過程，查找元素p所對應的集合編號 * O(h)復雜度，h為樹的高度 * 使用路徑壓縮 * @param p * @return */ private int find(int p) { if (p < 0 && p >= parent.length) { throw new IllegalArgumentException("p is illegal"); } if (p != parent[p]) { parent[p] = find(parent[p]); } return parent[p]; } /** * 查詢p, q是否同屬一個集合 * 時間復雜度O(h) * @param p * @param q * @return */ @Override public boolean isConnected(int p, int q) { return find(p) == find(q); } /** * 合并元素p, q所屬的集合，只需要把Rank低的根節點指向Rank高的根節點就可以 * O(h)復雜度 * @param p * @param q */ @Override public void unionElements(int p, int q) { int pRoot = find(p); int qRoot = find(q); if (pRoot == qRoot) { return; } //敗者食塵 if (rank[pRoot] < rank[qRoot]) { parent[pRoot] = qRoot; } else if (rank[qRoot] < rank[pRoot]) { parent[qRoot] = pRoot; } else { parent[qRoot] = pRoot; rank[pRoot] += 1; } }} |
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：https://blog.csdn.net/Nino_sama/article/details/101028903
