`
473687880
  • 浏览: 478453 次
文章分类
社区版块
存档分类
最新评论

并查集算法

 
阅读更多

最近在图论这一块总遇到判断连通问题,判断图是否连通,可以用两种简单的方法(我目前知道的)—并查集和DFS,其中并查集可能更好理解,并查集的思路:并查集可以分为两个过程一个是归并过程一个是查找过程,其中在一个图中,一开始声明一个bin数组把所有的结点都指向结点自己本身,也就是bin[i]=i;i代表结点的序号,之后每次遇到一条连通的道路,比如a-b首先需要把a和b指向的根的结点找出来(当然一开始的时候都指向自己,之后合并一些结点之后指向的就是某一个根结点了),之后把a的根结点数值指向b的根结点数值,如此反复之后,所有连通的点都指向一个根节点。代码如下:

#include<iostream>
int find(int t)
{
    r=t;
    while(bin[r]!=r)
    {
        r=bin[r];
    }
    return r;
}
void merge(int x,int y)
{
    int fx,fy;
    fx=find(x),fy=find(y);
    if(fx!=fy)
    {
        bin[fx]=fy;
    }
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics