算法来自Algorithms一书1.5节,在此备忘。
该书配套网站:http://algs4.cs.princeton.edu/15uf/
算法解决的问题
解决的是动态连通性问题,给定N个点和N个点之间的连通数据,例如:
N = 10(0,1,2,3,4,5,6,7,8,9)
连通数据:
(4,3)
(3,8)
(6,5)
(9,4)
(2,1)
(8,9)
(5,0)
(7,2)
(6,1)
(1,0)
(6,7)
效果图如下:
问题就是,如何判断给定的两个点是连通的?比如上图中,(8,9)、(1,0)、(6,7)都是连通的。如何判断这些节点中有多少个连通分量(孤岛,如上面的数据构成的节点就存在两个相互独立的孤岛)?
quick-find算法:
该算法的思路是创建一个长度为N的数组,数组的每一个元素表示一个点,依靠判断两个数组元素的值是否相同来判断这两个元素是否是连通的,数组元素的初始值为点的序号,表示他们互不相连。新加入一个连接时,需要将连接双方的每一个点的值都改成一致的。
public class QuickFindUF {
private int[] id;
private int count;
public QuickFindUF(int N){
id = new int[N];
for(int i = 0;i<N;i++){
id[i] = i;
}
count = N;
}
public int find(int p){
return id[p];
}
//union q to p
public void union(int p,int q){
int pId = find(p);
int qId = find(q);
if(pId==qId) return;
for(int i = 0;i<id.length;i++){
if(id[i]==qId){
id[i] = pId;
}
}
count--;
}
public boolean connected(int p,int q){
return find(p) == find(q);
}
public int count(){
return count;
}
public static void main(String[] args) {
int N = StdIn.readInt();
QuickFindUF uf = new QuickFindUF(N);
while(!StdIn.isEmpty()){
int p = StdIn.readInt();
int q = StdIn.readInt();
if(uf.connected(p, q)){
continue;
}
uf.union(p, q);
StdOut.println(p + " " + q);
}
StdOut.println(uf.count()+" compontents");
}
}
quick-union算法
quick-union算法在对节点值的定义上有所不同,表示的是父节点,从而把所有节点变成了树状结构。
quick-find算法的时间主要浪费在union上,改进的quick-union算法的union方法进行了优化,不需要遍历所有节点。这主要依赖于find方法,find方法查找的不是节点本身,而是节点所属的根节点:
public class QuickUnionUF {
private int[] id;
private int count;
public QuickUnionUF(int N){
id = new int[N];
for(int i = 0;i<N;i++){
id[i] = i;
}
count = N;
}
public int find(int p){
while(id[p]!=p){
p = id[p];
}
return id[p];
}
//union q to p
public void union(int p,int q){
int pId = find(p);
int qId = find(q);
if(pId==qId) return;
id[pId] = qId;
count--;
}
public boolean connected(int p,int q){
return find(p) == find(q);
}
public int count(){
return count;
}
public static void main(String[] args) {
int N = StdIn.readInt();
QuickUnionUF uf = new QuickUnionUF(N);
while(!StdIn.isEmpty()){
int p = StdIn.readInt();
int q = StdIn.readInt();
if(uf.connected(p, q)){
continue;
}
uf.union(p, q);
//StdOut.println(p + " " + q);
}
StdOut.println(uf.count()+" compontents");
}
}
加权重的quick-union算法
quick-union的缺点是,在最坏情况的输入数据时,最后形成的树可能是畸形的,树的深度很大,导致find方法查找根节点的时间代价越来越大。加权重的quick-union算法增加了每个节点的权重值。在初始时每个节点的权重是相同的,当节点不断地聚集,根节点的权重不断增大。union的时候,根据权重就能将小树连接到大树上,不会出现将大树连接到小树的情况,从而保证树的深度不会很大。
public class WeightedQuickUnionUF {
private int[] id;
private int[] weight;
private int count;
public WeightedQuickUnionUF(int N){
System.out.println("size=" +N);
id = new int[N];
weight = new int[N];
for(int i = 0;i<N;i++){
id[i] = i;
weight[i] = 1;
}
count = N;
}
public int find(int p){
while(id[p]!=p){
p = id[p];
}
return id[p];
}
//union q to p
public void union(int p,int q){
int pId = find(p);
int qId = find(q);
if(pId==qId) return;
if(weight[pId] < weight[qId]){
//connect p to q
id[pId] = qId;
weight[qId] += weight[pId];
}else{
//connect q to p
id[qId] = pId;
weight[pId] += weight[qId];
}
count--;
}
public boolean connected(int p,int q){
return find(p) == find(q);
}
public int count(){
return count;
}
public static void main(String[] args) {
int N = StdIn.readInt();
WeightedQuickUnionUF uf = new WeightedQuickUnionUF(N);
while(!StdIn.isEmpty()){
int p = StdIn.readInt();
int q = StdIn.readInt();
if(uf.connected(p, q)){
continue;
}
uf.union(p, q);
//StdOut.println(p + " " + q);
}
StdOut.println(uf.count()+" compontents");
}
}
总的来说,quick-find方法不是基于树来考虑的,跟多的是基于分组的思想,最终的结果是不同的孤岛中的点都保存着相同的组号。quick-union算法则是基于树的思想,两个树想连的时候,不会对树的子节点进行任何操作,仅仅是对树的根节点进行调整,这就避免了从新调整节点值的操作。这种情况下,如果再保证树的深度不是很大,就能迅速提高运行速度。
分享到:
相关推荐
leetcode 答案 算法 数据结构和算法实现 C++实现,使用Googletest框架测试 ...UnionFind.h │ ├── Hash │ │ └── Hash.h │ ├── Queue │ │ ├── DHeap.h │ │ ├── Deque
普林斯顿算法课程视频资源,这是一门经典的数据结构与算法课,免费,分上下两部分,上部分内容包括Union-Find, basic data structures(Array, LinkedList, Queue, Stack, prioprity queue, symbol table...), ...
学习的大部分基础数据结构和相关的算法 实现语言主要是C/C++ BST: 二分搜索树 BubbleSort: 冒泡排序 CircleLinkList: 循环链表 Expression: 表达式求值 ...UnionFind: 并查集 graph_dfs: 图的深度遍历
苦中排课程序内又包括了几种不同算法实现的程序,供学习参考。 Filename : ComplexSet.cpp Intro : This is a Class of Set whoes elements are complex Functions: (1)The Union of two Sets (overload ...
08-- 算法的#08--深入详解并查集union-find算法 09-- 算法#09--用简单的思维理解选择,插入,冒泡和希尔排序 10-- 算法#10--用简单的思维理解堆排序 算法# 用简单的思维理解归并排序和三向快速排序 12--
苦中排课程序内又包括了几种不同算法实现的程序,供学习参考。 Filename : ComplexSet.cpp Intro : This is a Class of Set whoes elements are complex Functions: (1)The Union of two Sets (overload operator...
iOS开发学习路线 语言 计算机基础 汇编 排序算法 链表 动态规划 红黑树 B树 二叉树 回溯算法 分治算法 贪心算法 枚举算法 Stack(栈) Array(数组) Heap(堆) Graph(图表) Tree(树) Hash Table(哈希表) ...
Algorithm templates and LeetCode SolutionsTBD Add multi binary search algorithm for leetcode0034 Add Segment Tree for data structure Add union-find algorithm(Disjoint Set Union) for data structure Add...
UnionFind 类的可信代码副本。 其次,我不熟悉 API。 我需要先记住所有的 API。 我还需要学习如何分析时间复杂度。 我需要练习写一个基于联合查找算法的解决方案,并在45分钟内完成。 我需要每周一
Arrays(数组)、Stacks(栈)、Queues(队列)、LinkedList(链表)、Recursion(递归思想)、BinarySearchTree(二分搜索树)、Set(集合)、Map(映射)、Heap(堆)、...SegmentTree(线段树)、Trie(字典树)、UnionFind(并查集)、AVLTree(AVL...
本书内容全面、翔实,是学习C++编程语言的广大学生的一部有用的工具书,也是对C++感兴趣的读者的必备参考书。 第一部分 C++基础:C子集 第1章 C语言概述 1.1 C语言的起源和历史 1.2 C语言是中级语言 1.3 C语言是...
这本书也不适合带领你学习面向对象(Object Oriented)技术 — 是的,STL 与面向对象没有太多关连。本书前言清楚说明了书籍的定位和合适的读者,以及各类基础读物。如果你的Generic Programming/STL实力足以阅读本书...
中的独立数据结构概述(union-find、trie 等)。 :常见的概率分布,PDF,CDF,模拟方法。 :通常有用但难以记住的 Python 技巧。 :高级张量流 API。 基本用例。 :更深入地研究特定的 ML 模型。 : 数据清洗、平滑...
下載網址: ... 中文名: 從新手到高手C++全方位學習隨書DVD文件 作者: 範磊 出版社: 科學出版社 書號: 703024706X 發行時間: 2009年09月 ...《從新手到高手C++全方位學習》總結了十幾本C++圖書及教材的優點,擯棄了它們語...