Java實(shí)現(xiàn)并查集
本文實(shí)例為大家分享了Java實(shí)現(xiàn)并查集的具體代碼,供大家參考,具體內(nèi)容如下
自下而上的樹(shù)結(jié)構(gòu)
接口
/** * @author Nino */public interface UF { int size(); /** * 看兩個(gè)元素是否相連 * @param p * @param q * @return */ boolean isConnected(int p, int q); /** * 將兩個(gè)元素合并在一起,變成一個(gè)集合中的元素 * @param p * @param q */ void unionElements(int p, int q);}
使用路徑壓縮的并查集
/** * @author Nino */public class UnionFind5 implements UF { private int[] parent; //rank[i]表示以i為根的集合中樹(shù)的層數(shù) 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; } /** * 查找過(guò)程,查找元素p所對(duì)應(yīng)的集合編號(hào) * O(h)復(fù)雜度,h為樹(shù)的高度 * 使用路徑壓縮 * @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是否同屬一個(gè)集合 * 時(shí)間復(fù)雜度O(h) * @param p * @param q * @return */ @Override public boolean isConnected(int p, int q) { return find(p) == find(q); } /** * 合并元素p, q所屬的集合,只需要把Rank低的根節(jié)點(diǎn)指向Rank高的根節(jié)點(diǎn)就可以 * O(h)復(fù)雜度 * @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; } }}
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持好吧啦網(wǎng)。
相關(guān)文章:
1. ASP新手必備的基礎(chǔ)知識(shí)2. asp文件用什么軟件編輯3. CentOS郵箱服務(wù)器搭建系列——SMTP服務(wù)器的構(gòu)建( Postfix )4. PHP基礎(chǔ)之生成器4——比較生成器和迭代器對(duì)象5. JAVA 實(shí)現(xiàn)延遲隊(duì)列的方法6. JS中6個(gè)對(duì)象數(shù)組去重的方法7. vue+element開(kāi)發(fā)一個(gè)谷歌插件的全過(guò)程8. Vue axios獲取token臨時(shí)令牌封裝案例9. 通過(guò)IEAD+Maven快速搭建SSM項(xiàng)目的過(guò)程(Spring + Spring MVC + Mybatis)10. 利用CSS制作3D動(dòng)畫

網(wǎng)公網(wǎng)安備