Union Find
动态链接:
这里union(x,y) 相当于一个函数，这个函数建立两个点，x，y的链接。而connected(x,y)用于检测两点的链接性，即是否处于链接状态.
connected(0,7)就是用于检测0,7这两点是否相连。
Union find能做很酷帅的事情，迷宫连通图的查找~
对链接性进行建模
把“链接” 等效为三种形式:
自身式: P 链接向P
双向式: P链接向Q，Q链接向P
传递式：P链接向Q，Q链接向R，于是我们说P链接向R
Union-find data type (API)
void union(int p, int q)
boolean connected(int p, int q)
抽象出两个API来对union-find data type进行操作
感觉这个API设计的还是不够合理（个人观点），仅仅靠输入的p，q是无法对所有元素操作的，意味着这里函数要额外的获取一个全局变量去多所有元素进行操作。而这对于函数的封装性是不好的.
函数应该尽可能少的去依赖除了入口参数以外的数据.当外部全局变量发生变化时不至于影响函数内部(函数内部如果没有依赖外部的全局变量的话)，从而提高函数的健壮性.
于是 API的入口更改如下:
void union_element(int* p_array,int size,int p, int q);
int connected_element(int* p_array,int size,int p,int q);
这里给出自己的C 语言实现
/*********************************************************
code writer : EOF
code date : 2014.09.07
code file : union_find.c
code version : 1.0
e-mail : [email protected]
code purpose :
A demo for union-find.
If there is something wrong with my code, please
touch me by e-mail. Thank you. :-)
**********************************************************/
#include <stdio.h>
#include <malloc.h>
#define SAME 1
#define DIFF 0
#define DEBUG
//----------------------------------------------------
void union_element(int* p_array,int size,int p, int q);
int connected_element(int* p_array,int size,int p,int q);
int root_element(int* p_array,int size,int index);
//----------------------------------------------------
int init_element(int* p_array,int size);
int main()
{
int num = 0;
int ret = 0;
int* all_element = NULL;
printf("Please input how many number in your union group\n");
while(!scanf("%d",&num))
{
getchar();
printf("scanf error, please input again\n");
}
all_element = (int*)malloc(sizeof(int) * num);
init_element(all_element,num);
/*
** It's time to test our API
*/
#ifdef DEBUG
union_element(all_element,num,4,3);
union_element(all_element,num,3,8);
union_element(all_element,num,6,5);
union_element(all_element,num,9,4);
union_element(all_element,num,2,1);
ret = connect_element(all_element,num,0,7);
if(ret == SAME)
{
printf("Y Connected!\n");
}
else if (ret == DIFF)
{
printf("X Unconnected!\n");
}
ret = connect_element(all_element,num,8,9);
if(ret == SAME)
{
printf("Y Connected!\n");
}
else if (ret == DIFF)
{
printf("X Unconnected!\n");
}
#endif
free(all_element);
all_element = NULL;
return 0;
}
int root_element(int* p_array,int size,int index)
{
if(!p_array)
{
printf("p_array is NULL!\nNeedless to initialize\n");
return -1;
}
if(index > (size-1))
{
printf("'index' bigger than size of array which 'p_array' point to.\n");
return -1;
}
/*
** Indexing until we get the root.
*/
for(;p_array[index] != index;)
{
index = p_array[index];
}
return index;
}
void union_element(int* p_array,int size,int p, int q)
{
if(!p_array)
{
printf("function:%s line: %d p_array is NULL\n",__FUNCTION__,__LINE__);
return ;
}
if(p > (size-1) || q > (size-1))
{
printf("index 'p' 'q' are bigger than the max size of array\n");
printf("p: %3d q: %3d",p,q);
return ;
}
int p_union = p_array[p];
int q_union = p_array[q];
int tmp = 0;
/*
** Connect the "union-p" into "union-q."
*/
p_array[p] = q_union;
}
int connect_element(int* p_array,int size,int p ,int q)
{
if(!p_array)
{
printf("function:%s line: %d p_array is NULL\n",__FUNCTION__,__LINE__);
return -1;
}
if(p > (size-1) || q > (size-1))
{
printf("index 'p' 'q' are bigger than the max size of array\n");
printf("p: %3d q: %3d",p,q);
return ;
}
if(root_element(p_array,size,p) == root_element(p_array,size,q))
{
return SAME;
}
else
{
return DIFF;
}
}
int init_element(int* p_array,int size)
{
if(!p_array)
{
printf("p_array is NULL!\nNeedless to initialize\n");
return -1;
}
int tmp = 0;
/*
** Set id of each objects to itself,
*/
for(tmp = 0; tmp < size; tmp++)
{
p_array[tmp] = tmp;
}
}
上述的quick find方法还是比较慢，下面对quick find进行改进，降低算法的时间复杂度
对之前union的策略进行改进.
/*********************************************************
code writer : EOF
code date : 2014.09.07
code file : quick_union.c
code version : 1.0v
e-mail : [email protected]
code purpose :
A demo for quick-union.
If there is something wrong with my code, please
touch me by e-mail. Thank you. :-)
**********************************************************/
#include <stdio.h>
#include <malloc.h>
#define SAME 1
#define DIFF 0
#define DEBUG
//--------------------------------------------------------------
int quick_root_element(int* p_array,int size,int index);
void quick_union_element(int* p_array,int size,int p, int q);
int quick_connected_element(int* p_array,int size,int p,int q);
//--------------------------------------------------------------
int init_element(int* p_array,int size);
int print_union(int* p_array,int size);
int main()
{
int num = 0;
int ret = 0;
int* all_element = NULL;
printf("Please input how many number in your union group\n");
while(!scanf("%d",&num))
{
getchar();
printf("scanf error, please input again\n");
}
all_element = (int*)malloc(sizeof(int) * num);
if(init_element(all_element,num) < 0)
{
return 0;
}
#ifdef DEBUG
if(num < 10)
{
return 0;
}
quick_union_element(all_element,num,2,9);
quick_union_element(all_element,num,4,3);
quick_union_element(all_element,num,2,4);
quick_union_element(all_element,num,5,6);
printf("Before union(6,9)\n");
print_union(all_element,num);
printf("After union(6,9)\n");
quick_union_element(all_element,num,6,9);
print_union(all_element,num);
#endif
free(all_element);
all_element = NULL;
return 0;
}
#ifndef DEBUG
int print_union(int* p_array,int size)
{
if(!p_array)
{
printf("function:%s line:%d 'p_array' is NULL\n",__FUNCTION__,__LINE__);
return -1;
}
int tmp = 0;
for(tmp = 0; tmp < size;tmp++)
{
printf("%2d ",p_array[tmp]);
}
printf("\n");
}
#else
int print_union(int* p_array,int size)
{
int ret_tmp = 0;
int ret_grp = 0;
if(!p_array)
{
printf("function:%s line:%d 'p_array' is NULL\n",__FUNCTION__,__LINE__);
return -1;
}
int tmp = 0;
int grp = 0;
for(grp = 0;grp < size; grp++)
{
for(tmp = 0;tmp < size; tmp++)
{
if(tmp == 0)
{
printf("######### group :%d ##########\n",grp);
}
ret_tmp = quick_root_element(p_array,size,tmp);
ret_grp = quick_root_element(p_array,size,grp);
if(ret_grp != grp)
{
/*
** We need not to print out the same message on the screen.
*/
break;
}
/*
** Check error.
*/
if(ret_tmp < 0 || ret_grp < 0)
{
return 0;
}
if(ret_tmp == ret_grp)
{
printf("%3d ",tmp);
}
}
printf("\n");
}
return 0;
}
#endif
int quick_root_element(int* p_array,int size,int index)
{
if(!p_array)
{
printf("p_array is NULL!\nNeedless to initialize\n");
return -1;
}
if(index > (size-1))
{
printf("'index' bigger than size of array which 'p_array' point to.\n");
return -1;
}
for(;p_array[index] != index;)
{
index = p_array[index];
}
return index;
}
int init_element(int* p_array,int size)
{
if(!p_array)
{
printf("p_array is NULL!\nNeedless to initialize\n");
return -1;
}
int tmp = 0;
for(tmp = 0; tmp < size; tmp++)
{
p_array[tmp] = tmp;
}
return 0;
}
void quick_union_element(int* p_array,int size,int p, int q)
{
if(!p_array)
{
printf("function:%s line: %d p_array is NULL\n",__FUNCTION__,__LINE__);
return ;
}
if(p > (size-1) || q > (size-1))
{
printf("index 'p' 'q' are bigger than the max size of array\n");
printf("p: %3d q: %3d",p,q);
return ;
}
int root_p_union = 0;
if((root_p_union = quick_root_element(p_array,size,p)) < 0)
{
return;
}
int root_q_union = 0;
if((root_q_union = quick_root_element(p_array,size,q)) < 0)
{
return;
}
p_array[root_q_union] = root_p_union;
}
int quick_connect_element(int* p_array,int size,int p ,int q)
{
int ret_p = 0;
int ret_q = 0;
if(!p_array)
{
printf("function:%s line: %d p_array is NULL\n",__FUNCTION__,__LINE__);
return -1;
}
if(p > (size-1) || q > (size-1))
{
printf("index 'p' 'q' are bigger than the max size of array\n");
printf("p: %3d q: %3d",p,q);
return ;
}
ret_p = quick_root_element(p_array,size,p);
ret_q = quick_root_element(p_array,size,q);
if(ret_p < 0|| ret_q < 0)
{
return -1;
}
else if(ret_q == ret_p)
{
return SAME;
}
else
{
return DIFF;
}
}
改进1: 添加union分支的权重
保证规模小的union 树成为规模大的union 树的子树
为描述权重这个概念，我们添加一个变量——sz[ ] 数组,所有的初始树深度都是 1
quick-union 会导致树的深度很深
而weighted QU相对来说要好很多
这里我实在受不了接口参数达到四个甚至四个以上了！
用structure封装。这里我修改了所有我上面实现的关于union-find的API入口参数，以求达到抽象简洁.
encapsulation 很光辉的思想
/*********************************************************
code writer : EOF
code date : 2014.09.07
code file : weighted_QU.c
code version : 1.0v
e-mail : [email protected]
code purpose :
A demo for weighted quick-union.
If there is something wrong with my code, please
touch me by e-mail. Thank you. :-)
**********************************************************/
#include <stdio.h>
#include <malloc.h>
#define SAME 1
#define DIFF 0
#define INIT_DEPTH 1
#define DEBUG
//#define DEBUG_DEPTH
struct union_element
{
int index;
int depth;
};
//-------------------------------------------------------------------------------------
int quick_root_element(struct union_element* p_array,int size,int index);
void quick_union_element(struct union_element* p_array,int size,int p, int q);
int quick_connected_element(struct union_element* p_array,int size,int p,int q);
//-------------------------------------------------------------------------------------
int init_element(struct union_element* p_array,int size);
int print_union(struct union_element* p_array,int size);
int main()
{
int num = 0;
int ret = 0;
struct union_element* all_element = NULL;
printf("Please input how many number in your union group\n");
while(!scanf("%d",&num))
{
getchar();
printf("scanf error, please input again\n");
}
all_element = (struct union_element*)malloc(sizeof(struct union_element) * num);
if(init_element(all_element,num) < 0)
{
return 0;
}
#ifdef DEBUG
if(num < 10)
{
return 0;
}
quick_union_element(all_element,num,2,9);
quick_union_element(all_element,num,4,3);
quick_union_element(all_element,num,2,4);
quick_union_element(all_element,num,5,6);
printf("Before union(6,9)\n");
print_union(all_element,num);
printf("After union(6,9)\n");
quick_union_element(all_element,num,6,9);
print_union(all_element,num);
#endif
free(all_element);
all_element = NULL;
return 0;
}
/*
** There are two different print_union() you could use.
** If you want to debug and use the second one, just change
** Macro"#ifdef" into "#ifndef". :)
*/
#ifndef DEBUG
int print_union(struct union_element* p_array,int size)
{
if(!p_array)
{
printf("function:%s line:%d 'p_array' is NULL\n",__FUNCTION__,__LINE__);
return -1;
}
int tmp = 0;
for(tmp = 0; tmp < size;tmp++)
{
printf("%2d ",p_array[tmp].index);
}
printf("\n");
}
#else
int print_union(struct union_element* p_array,int size)
{
int ret_tmp = 0;
int ret_grp = 0;
if(!p_array)
{
printf("function:%s line:%d 'p_array' is NULL\n",__FUNCTION__,__LINE__);
return -1;
}
int tmp = 0;
int grp = 0;
for(grp = 0;grp < size; grp++)
{
for(tmp = 0;tmp < size; tmp++)
{
if(tmp == 0)
{
printf("######### group :%d ##########\n",grp);
}
ret_tmp = quick_root_element(p_array,size,tmp);
ret_grp = quick_root_element(p_array,size,grp);
if(ret_grp != grp)
{
/*
** We need not to print out the same message on the screen.
*/
break;
}
/*
** Check error.
*/
if(ret_tmp < 0 || ret_grp < 0)
{
return 0;
}
if(ret_tmp == ret_grp)
{
printf("%3d ",tmp);
}
}
printf("\n");
}
return 0;
}
#endif
int quick_root_element(struct union_element* p_array,int size,int index)
{
if(!p_array)
{
printf("p_array is NULL!\n");
return -1;
}
if(index > (size-1))
{
printf("'index' bigger than size of array which 'p_array' point to.\n");
return -1;
}
for(;p_array[index].index != index;)
{
index = p_array[index].index;
}
return index;
}
int init_element(struct union_element* p_array,int size)
{
if(!p_array)
{
printf("p_array is NULL!\nNeedless to initialize\n");
return -1;
}
int tmp = 0;
for(tmp = 0; tmp < size; tmp++)
{
p_array[tmp].index = tmp;
p_array[tmp].depth = INIT_DEPTH;
}
return 0;
}
void quick_union_element(struct union_element* p_array,int size,int p, int q)
{
if(!p_array)
{
printf("function:%s line: %d p_array is NULL\n",__FUNCTION__,__LINE__);
return ;
}
if(p > (size-1) || q > (size-1))
{
printf("index 'p' 'q' are bigger than the max size of array\n");
printf("p: %3d q: %3d",p,q);
return ;
}
int root_p_union = 0;
if((root_p_union = quick_root_element(p_array,size,p)) < 0)
{
return;
}
int root_q_union = 0;
if((root_q_union = quick_root_element(p_array,size,q)) < 0)
{
return;
}
#ifdef DEBUG_DEPTH
printf("\n\n%3d ",p_array[root_p_union].depth);
printf("%3d \n\n",p_array[root_q_union].depth);
#endif
/*
** Weighting and unioning !
*/
if(p_array[root_q_union].depth < p_array[root_p_union].depth)
{
p_array[root_q_union].index = root_p_union;
p_array[root_p_union].depth += p_array[root_q_union].depth;
}
else
{
p_array[root_p_union].index = root_q_union;
p_array[root_q_union].depth += p_array[root_p_union].depth;
}
}
int quick_connect_element(struct union_element* p_array,int size,int p ,int q)
{
int ret_p = 0;
int ret_q = 0;
if(!p_array)
{
printf("function:%s line: %d p_array is NULL\n",__FUNCTION__,__LINE__);
return -1;
}
if(p > (size-1) || q > (size-1))
{
printf("index 'p' 'q' are bigger than the max size of array\n");
printf("p: %3d q: %3d",p,q);
return ;
}
ret_p = quick_root_element(p_array,size,p);
ret_q = quick_root_element(p_array,size,q);
if(ret_p < 0|| ret_q < 0)
{
return -1;
}
else if(ret_q == ret_p)
{
return SAME;
}
else
{
return DIFF;
}
}
改进2:路径压缩
路径压缩的实现方法很简单，这里不再给出完全实现，仅给出算法思想
即修改root()函数即可
int root(int i)
{
while (i != id[i])
{
id[i] = id[id[i]];
i = id[i];
}
return i;
}