算法:图解最小生成树之克鲁斯卡尔(Kruskal)算法

我们在前面讲过的《克里姆算法》是以某个顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树的。同样的思路,我们也可以直接就以边为目标去构建,因为权值为边上,直接找最小权值的边来构建生成树也是很自然的想法,只不过构建时要考虑是否会形成环而已,此时我们就用到了图的存储结构中的边集数组结构,如图7-6-7

假设现在我们已经通过邻接矩阵得到了边集数组edges并按权值从小到大排列如上图。

下面我们对着程序和每一步循环的图示来看:

算法代码:(改编自《大话数据结构》)

typedef struct
{
    int begin;
    int end;
    int weight;
} Edge;

/* 查找连线顶点的尾部下标 */
int Find(int *parent, int f)
{
    while (parent[f] > 0)
        f = parent[f];

    return f;
}
/* 生成最小生成树 */
void MiniSpanTree_Kruskal(MGraph G)
{
    int i, j, n , m;
    int k = 0;
    int parent[MAXVEX];/* 定义一数组用来判断边与边是否形成环路 */

    Edge edges[MAXEDGE];/* 定义边集数组,edge的结构为begin,end,weight,均为整型 */

    /* 此处省略将邻接矩阵G转换为边集数组edges并按权由小到大排列的代码*/
    for (i = 0; i < G.numVertexes; i++)
        parent[i] = 0;

    cout << "打印最小生成树:" << endl;
    for (i = 0; i < G.numEdges; i++)/* 循环每一条边 */
    {
        n = Find(parent, edges[i].begin);
        m = Find(parent, edges[i].end);
        if (n != m)/* 假如n与m不等,说明此边没有与现有的生成树形成环路 */
        {
            parent[n] = m;/* 将此边的结尾顶点放入下标为起点的parent中。 */
            /* 表示此顶点已经在生成树集合中 */

            cout << "(" << edges[i].begin << ", " << edges[i].end << ") "
                 << edges[i].weight << endl;
        }
    }

}

1、程序 第17~28行是初始化操作,中间省略了一些存储结构转换代码。

2、第30~42行,i = 0 第一次循环,n = Find( parent, 4) = 4; 同理 m = 7; 因为 n != m 所以parent[4] = 7, 并且打印 “ (4, 7) 7  ” 。此时我们已经将边(v4, v7)纳入到最小生成树中,如下图的第一个小图。

3、继续循环,当i从1 至 6 时,分别把(v2, v8), (v0, v1), (v0, v5), (v1, v8), (v3, v7), (v1, v6)纳入到最小生成树中,如下图所示,此时parent数组为

{ 1, 5, 8, 7, 7, 8, 0, 0, 6 },如何解读现在这些数字的意义呢?从图i = 6来看,其实是有两个连通的边集合A与B 纳入到最小生成树找中的,如图7-6-12所示。parent[0] = 1表示v0 和v1 已经在生成树的边集合A中,将parent[0] = 1中的 1 改成下标,由parent[1] = 5 ,表示v1 和v5 已经在生成树的边集合A中,parent[5] = 8 ,表示v5 和v8 已经在生成树的边集合A中,parent[8] = 6 ,表示v8 和v6 已经在生成树的边集合A中,parent[6] = 0 表示集合A暂时到头,此时边集合A有 v0, v1, v5, v6, v8。查看parent中没有查看的值,parent[2] = 8,表明v2 和 v8在一个集合中,即A中。再由parent[3] = 7, parent[4] = 7 和 parent[7] = 0 可知v3, v4, v7 在一个边集合B中。

4、当i = 7时, 调用Find函数,n = m = 6,不再打印,继续下一循环,即告诉我们,因为(v5, v6) 使得边集合A形成了回路,因此不能将其纳入生成树中,如图7-6-12所示。

5、当i = 8时与上面相同,由于边(v1, v2) 使得边集合A形成了回路,因此不能将其纳入到生成树中,如图7-6-12所示。

6、当i = 9时,n = 6, m = 7, 即parent[6] = 7,打印“(6, 7)19” ,此时parent数组为{ 1, 5, 8, 7, 7, 8, 7, 0, 6 } ,如图7-6-13所示。

最后,我们来总结一下克鲁斯卡尔算法的定义:

假设 N = (V, {E} )是连通网,则令最小生成树的初始状态为只有n个顶点而无边的非连通图T { V, {} },图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将其加入到 T 中,否则舍去此边而选择下一条代价最小的边。依次类推,直至T中所有顶点都在同一连通分量上为止。

此算法的Find函数由边数e决定,时间复杂度为O(loge),而外面有一个for循环e次,所以克鲁斯卡尔算法的时间复杂度为O(eloge)。

对比普里姆和克鲁斯卡尔算法,克鲁斯卡尔算法主要针对边来展开,边数少时效率比较高,所以对于稀疏图有较大的优势;而普里姆算法对于稠密图,即边数非常多的情况下更好一些。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

1003. 猜数游戏 (Standard IO)

题目描述 有一个“就是它”的猜数游戏,步骤如下:请你对任意输入的一个三位数x,在这三位数后重复一遍,得到一个六位数,467-->467467.把这个数连续除以7...

3648
来自专栏尾尾部落

[剑指offer] 跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

842
来自专栏C语言及其他语言

【每日一题】1426: [蓝桥杯][历届试题]九宫重排

如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面...

1053
来自专栏Java3y

Map集合、散列表、红黑树介绍

1703
来自专栏calmound

HDU 3652 B-number(数位DP)

http://acm.hdu.edu.cn/showproblem.php?pid=3652 题意:类似3555,0-n之间某个数中包含13,且整个数能被13...

3416
来自专栏程序员互动联盟

【编程之美】最短路径

最短路径 任意给定两个数字A和B,通过将A和6个数(7,-7,5,-5,12,-12)做加减运算,运算次数不限,每个数可以被使用多次,求从A到B最少要经过多少次...

3996
来自专栏和蔼的张星的图像处理专栏

2. 尾部的零

设计一个算法,计算出n阶乘中尾部零的个数 样例 11! = 39916800,因此应该返回 2. 这其实是一个数学题,思路倒是很简单,主要就是找每个数有多...

1223
来自专栏zaking's

用js来实现那些数据结构15(图01)

1794
来自专栏数据结构与算法

BZOJ3143: [Hnoi2013]游走(期望DP 高斯消元)

Description 一个无向连通图,顶点从1编号到N,边从1编号到M。  小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当...

4516
来自专栏WD学习记录

牛客网 和为S的连续正数序列

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100...

1451

扫码关注云+社区

领取腾讯云代金券