java编程实现并查集的路径压缩代码详解
首先看两张路径压缩的图片: 并查集(Union-find Sets)是一种非常精巧而实用的数据结构,它主要用于处理一些不相交集合的合并问题。一些常见的用途有求连通子图、求最小生成树的 Kruskal 算法和求最近公共祖先(Least Common Ancestors,LCA)等。 使用并查集时,首先会存在一组不相交的动态集合 S={S 1,S 2,⋯,S k } ,一般都会使用一个整数表示集合中的一个元素。 并查集的基本操作有三个: makeSet(s):建立一个新的并查集,其中包含 s 个单元素集合。 package com.dataStructure.union_find; // 我们的第五版Union-Find public class UnionFind5 { // rank[i]表示以i为根的集合所表示的树的层数 // 在后续的代码中,我们并不会维护rank的语意,也就是rank的值在路径压缩的过程中,有可能不在是树的层数值 // 这也是我们的rank不叫height或者depth的原因,他只是作为比较的一个标准 private int[] rank; private int[] parent; // parent[i]表示第i个元素所指向的父节点 private int count; // 数据个数 // 构造函数 public UnionFind5(int count){ rank = new int[count]; parent = new int[count]; this.count = count; // 初始化,每一个parent[i]指向自己,表示每一个元素自己自成一个集合 for( int i = 0 ; i < count ; i ++ ){ parent[i] = i; rank[i] = 1; } } // 查找过程,查找元素p所对应的集合编号 // O(h)复杂度,h为树的高度 private int find(int p){ assert( p >= 0 && p < count ); // path compression 1 while( p != parent[p] ){ parent[p] = parent[parent[p]]; p = parent[p]; } return p; // path compression 2,递归算法 // if( p != parent[p] ) // parent[p] = find( parent[p] ); // return parent[p]; } // 查看元素p和元素q是否所属一个集合 // O(h)复杂度,h为树的高度 public boolean isConnected( int p,int q ){ return find(p) == find(q); } // 合并元素p和元素q所属的集合 // O(h)复杂度,h为树的高度 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{ // rank[pRoot] == rank[qRoot] parent[pRoot] = qRoot; rank[qRoot] += 1; // 此时,我维护rank的值 } } } 总结 以上就是本文关于java编程实现并查集的路径压缩代码详解的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持! (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |