你好,欢迎访问我的博客!登录
当前位置:首页 - 技术 - 正文 君子好学,自强不息!

克鲁斯卡尔算法复杂度与并查集

2018-06-14 11:01:39技术admin36°c
A+ A-

克鲁斯卡尔算法的基本思想是以边为主导地位,始终选择当前可用(所选的边不能构成回路)的最小权植边。所以Kruskal算法的第一步是给所有的边按照从小到大的顺序排序。这一步可以直接使用库函数qsort或者sort。接下来从小到大依次考察每一条边(u,v)。

给定一股无向联通带权图G(V,E).E 中的每一条边(v,w)权值位C(v,w)。如果G的子图G'是一个包含G中所有定点的子图,那么G'称为G的生成树,如果G'的边的权值最小


那么G'称为G的最小生成树。


kruskal算法的基本思想:


1.首先将G的n个顶点看成n个孤立的连通分支(n个孤立点)并将所有的边按权从小大排序。


2.按照边权值递增顺序,如果加入边后存在圈则这条边不加,直到形成连通图


对2的解释:如果加入边的两个端点位于不同的连通支,那么这条边可以顺利加入而不会形成圈


本例中用到的图:


权值递增排序:


kruskal加边后情况:


所以对于任意边(u,v)要判断这两个点是不是存在于同一个连通支里。


  如果是,则舍弃这条边,接着判断另一条边


  如果不是,则把这条边加入到图中,并且把u,v属于的连通支合并


然后操作下一条边


这个算法执行的过程就是按照规定一个个连通支合并的过程,使最后只剩一个连通支。


What kind of data structure supportssuch operations?


这是一个值得思考的问题、、、逛社区的时候,有用链表的、二维数组的、、这里不讨论这些存储结构的可行性


这里要讨论的是有向树的存储

具体实现过程如下:

<1> 设一个有n个顶点的连通网络为G(V,E),最初先构造一个只有n个顶点,没有边的非连通图T={V,空},图中每个顶点自成一格连通分量。

<2> 在E中选择一条具有最小权植的边时,若该边的两个顶点落在不同的连通分量上,则将此边加入到T中;否则,即这条边的两个顶点落到同一连通分量      上,则将此边舍去(此后永不选用这条边),重新选择一条权植最小的边。

<3> 如此重复下去,直到所有顶点在同一连通分量上为止。

下面是伪代码


// 把所有边排序,记第i小的边为e[i] (1<=i<=m)m为边的个数 
// 初始化MST为空
// 初始化连通分量,使每个点各自成为一个独立的连通分量
for (int i = 0; i < m; i++)
{
    if (e[i].u和e[i].v不在同一连通分量)
    {
        // 把边e[i]加入MST
        // 合并e[i].u和e[i].v所在的连通分量 
    } 
}

Kruskal算法动态演示图

上面的伪代码,最关键的地方在于“连通分量的查询和合并”,需要知道任意两个点是否在同一连通分量中,还需要合并两个连通分量。

这个问题正好可以用并查集完美的解决(不得不佩服前辈们聪明才智啊!)

并查集(Union-Find set)这个数据结构可以方便快速的解决这个问题。基本的处理思想是:初始时把每个对象看作是一个单元素集合;然后依次按顺序读入联通边,将连通边中的两个元素合并。在此过程中将重复使用一个搜索(Find)运算,确定一个集合在那个集合中。当读入一个连通边(u,v)时,先判断u和v是否在同一个集合中,如果是则不用合并;如果不是,则用一个合并(Union)运算把u、v所在集合合并,使得这两个集合中的任意两个元素都连通。因此并查集在处理时,主要用到搜索和合并两个运算。

为了方便并查集的描述与实现,通常把先后加入到一个集合中的元素表示成一个树结构,并用根结点的序号来表示这个集合。因此定义一个parent[n]的数组,parent[i]中存放的就是结点i所在的树中结点i的父亲节点的序号。例如,如果parent[4]=5,就是说4号结点的父亲结点是5号结点。约定:如果i的父结点(即parent[i])是负数,则表示结点i就是它所在的集合的根结点,因为集合中没有结点的序号是负的;并且用负数的绝对值作为这个集合中所含结点的个数。例如,如果parent[7]=-4,说明7号结点就是它所在集合的根结点,这个集合有四个元素。初始时结点的parent值为-1(每个结点都是根结点,只包含它自己一个元素)。

实现Kruskal算法数据结构主要有3个函数。

void UFset() // 初始化 
{
    for (int i = 0; i < n; i ++)
        parent[i] = -1;
} 
int Find(int x)  // 查找并返回结点x所属集合的根结点 
{
    int s;    // 查找位置 
    for (s = x; parent[s]>=0; s = parent[s]);  // 注意这里的 ; 
    while (s != x)   // 优化方案 -- 压缩路径,使后续的查找 
    {
        int tmp = parent[x];
        parent[x] = s;
        x = tmp;
    }
    return s;
}
// R1和R2是两个元素,属于两个不同的集合,现在合并这两个集合
void Union (int R1, int R2)
{
    // r1位R1的根结点,r2位R2的根结点
    int r1 = Find(R1), r2 = Find(R2);
    int tmp = parent[r1] + parent[r2];   // 两个集合的结点个数之和(负数) 
    // 如果R2所在树结点个数 > R1所在树结点个数
    // 注意parent[r1]和parent[r2]都是负数
    if(parent[r1] > parent[r2])    // 优化方案 -- 加权法则 
    {
        parent[r1] = r2;        // 将根结点r1所在的树作为r2的子树(合并) 
        parent[r2] = tmp;       // 跟新根结点r2的parent[]值 
    }
    else
    {
        parent[r2] = r1;         // 将根结点r2所在的树作为r1的子树(合并) 
        parent[r1] = tmp;        // 跟新根结点r1的parent[]值 
    } 
}

接下来对 Find 函数和 Union 函数的实现过程作详细解释。

Find 函数:在 Find 函数中如果仅仅靠一个循环来直接得到结点所属集合的根结点的话,通过多次的 Union 操作就会有很多结点在树的比较深层次中,再查找起来就会很费时。可以通过压缩路径来加快后续的查找速度:增加一个 While 循环,每次都把从结点 x 到集合根结点的路径上经过的结点直接设置为根结点的子女结点。虽然这增加了时间,但以后的查找会更快。如图 3.4 所示,假设从结点 x = 6 开始压缩路径,则从结点 6 到根结点1 的路径上有 3 个结点:6、10、8,压缩后,这 3 个结点都直接成为根结点的子女结点,如图(b)所示。

并查集:Find函数中的路径压缩

Union 函数:两个集合并时,任一方可做为另一方的子孙。怎样来处理呢,现在一般采用加权合并,把两个集合中元素个数少的根结点做为元素个数多的根结点的子女结点。这样处理有什么优势呢?直观上看,可以减少树中的深层元素的个数,减少后续查找时间。

例如,假设从 1 开始到 n,不断合并第 i 个结点与第 i+1 个结点,采用加权合并思路的过程如下图所示(各子树根结点上方的数字为其 parent[ ]值)。这样查找任一结点所属集合的时间复杂度几乎都是 O(1)!!!

并查集:加权合并

不用加权规则可能会得到下图所示的结果。这就是典型的退化树(只有一个叶结点,且每个非叶结点只有一个子结点)现象,再查找起来就会很费时,例如查找结点 n 的根结点时复杂度为 O(n)。

并查集:合并时不加权的结果。

例 利用 Kruskal 算法求无向网的最小生成树,并输出依次选择的各条边及最终求得的最小生成树的权。

假设数据输入时采用如下的格式进行输入:首先输入顶点个数 n 和边数 m,然后输入 m 条边的数据。每条边的数据格式为:u v w,分别表示这条边的两个顶点及边上的权值。顶点序号从 1开始计起。

分析:

在下面的代码中,首先读入边的信息,存放到数组 edges[ ]中,并按权值从小到大进行排序。

Kruskal( )函数用于实现 :首先初始化并查集,然后从 edges[ ]数组中依次选用每条边,如果这条边的两个顶点位于同一个连通分量,则要弃用这条边;否则合并这两个顶点所在的连通分量。

代码如下:

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAXN 11  //顶点个数的最大值
#define MAXM 20  //边的个数的最大值
using namespace std; 
struct edge  //边
{
    int u, v, w; //边的顶点、权值
}edges[MAXM]; //边的数组
int parent[MAXN];  //parent[i]为顶点 i 所在集合对应的树中的根结点
int n, m;  //顶点个数、边的个数
int i, j;  //循环变量
void UFset( )  //初始化
{
    for( i=1; i<=n; i++ ) 
        parent[i] = -1;
}
int Find( int x ) //查找并返回节点 x 所属集合的根结点
{
    int s; //查找位置
    for( s=x; parent[s]>=0; s=parent[s] );
    while( s!=x ) //优化方案―压缩路径,使后续的查找操作加速。
    {
        int tmp = parent[x];
        parent[x] = s;
        x = tmp;
    }
    return s;
}
//将两个不同集合的元素进行合并,使两个集合中任两个元素都连通
void Union( int R1, int R2 )
{
    int r1 = Find(R1), r2 = Find(R2); //r1 为 R1 的根结点,r2 为 R2 的根结点
    int tmp = parent[r1] + parent[r2]; //两个集合结点个数之和(负数)
    //如果 R2 所在树结点个数 > R1 所在树结点个数(注意 parent[r1]是负数)
    if( parent[r1] > parent[r2] ) //优化方案――加权法则
    {
        parent[r1] = r2; 
        parent[r2] = tmp;
    }
    else
    {
        parent[r2] = r1; 
        parent[r1] = tmp;
    }
}
bool cmp( edge a, edge b ) //实现从小到大排序的比较函数
{
    return a.w <= b.w;
}
void Kruskal( )
{
    int sumweight = 0;  //生成树的权值
    int num = 0;  //已选用的边的数目
    int u, v;  //选用边的两个顶点
    UFset( ); //初始化 parent[]数组
    for( i=0; i<m; i++ )
    {
        u = edges[i].u; v = edges[i].v;
        if( Find(u) != Find(v) )
        {
            printf( "%d %d %d\n", u, v, edges[i].w );
            sumweight += edges[i].w; num++;
            Union( u, v );
        }
        if( num>=n-1 ) break;
    }
    printf( "weight of MST is %d\n", sumweight );
}
int main( )
{
    int u, v, w; //边的起点和终点及权值
    scanf( "%d%d", &n, &m ); //读入顶点个数 n
    for( int i=0; i<m; i++ )
    {
    scanf( "%d%d%d", &u, &v, &w ); //读入边的起点和终点
    edges[i].u = u; edges[i].v = v; edges[i].w = w;
    }
    sort(edges,edges+m,cmp);
    Kruskal();
    return 0;
}


  选择打赏方式
微信赞助

打赏

QQ钱包

打赏

支付宝赞助

打赏

  选择分享方式
  移步手机端
克鲁斯卡尔算法复杂度与并查集

1、打开你手机的二维码扫描APP
2、扫描左则的二维码
3、点击扫描获得的网址
4、可以在手机端阅读此文章
标签:

发表评论

选填

必填

必填

选填

请拖动滑块解锁
>>


  用户登录