首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法:图解最小生成树之克鲁斯卡尔(Kruskal)算法

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

作者头像
s1mba
发布2018-01-12 17:14:40
2.1K0
发布2018-01-12 17:14:40
举报
文章被收录于专栏:开发与安全开发与安全

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

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

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2013-04-30 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档