首页 > 代码库 > Union Find
Union Find
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 e-mail : jasonleaster@gmail.com 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 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; } 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; for(tmp = 0; tmp < size ;tmp++) { if(p_array[tmp] == p_union) { p_array[tmp] = 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(p_array[p] == p_array[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; for(tmp = 0; tmp < size; tmp++) { p_array[tmp] = tmp; } }
waiting for update...
Union Find
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。