算法:图解最小生成树之普里姆(Prim)算法

我们在图的定义中说过,带有权值的图就是网结构。一个连通图的生成树是一个极小的连通子图,它含有图中全部的顶点,但只有足以构成一棵树的n-1条边。所谓的最小成本,就是n个顶点,用n-1条边把一个连通图连接起来,并且使得权值的和最小。综合以上两个概念,我们可以得出:构造连通网的最小代价生成树,即最小生成树(Minimum Cost Spanning Tree)。

找连通图的最小生成树,经典的有两种算法,普里姆算法和克鲁斯卡尔算法,这里介绍普里姆算法。

为了能够讲明白这个算法,我们先构造网图的邻接矩阵,如图7-6-3的右图所示。

也就是说,现在我们已经有了一个存储结构为MGraph的MG(见《邻接矩阵创建图》)。MG有9个顶点,它的二维数组如右图所示,数组中我们使用65535代表无穷。

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

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

/* Prim算法生成最小生成树  */
void MiniSpanTree_Prim(MGraph MG)
{
    int min, i, j, k;
    int adjvex[MAXVEX];/* 保存相关顶点下标 */
    int lowcost[MAXVEX];/* 保存相关顶点间边的权值 */
    lowcost[0] = 0;/* 初始化第一个权值为0,即v0加入生成树 */
    /* lowcost的值为0,在这里就是此下标的顶点已经加入生成树 */
    adjvex[0] = 0;/* 初始化第一个顶点下标为0 */
    cout << "最小生成树的边为:" << endl;
    for (i = 1; i < MG.numVertexes; i++)
    {
        lowcost[i] = MG.arc[0][i];/* 将v0顶点与之有边的权值存入数组 */
        adjvex[i] = 0;/* 初始化都为v0的下标 */
    }

    for (i = 1; i < MG.numVertexes; i++)
    {
        min = INFINITY; /* 初始化最小权值为∞, */

        j = 1;
        k = 0;

        while (j < MG.numVertexes)/* 循环全部顶点 */
        {
            if (lowcost[j] != 0 && lowcost[j] < min)/* 如果权值不为0且权值小于min */
            {
                min = lowcost[j];/* 则让当前权值成为最小值 */
                k = j;/* 将当前最小值的下标存入k */
            }

            j++;
        }

        cout << "(" << adjvex[k] << ", " << k << ")" << "  "; /* 打印当前顶点边中权值最小的边 */
        lowcost[k] = 0;/* 将当前顶点的权值设置为0,表示此顶点已经完成任务 */

        for (j = 1; j < MG.numVertexes; j++)/* 循环所有顶点 */
        {
            /* 如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */
            if (lowcost[j] != 0 && MG.arc[k][j] < lowcost[j])
            {
                lowcost[j] = MG.arc[k][j];/* 将较小的权值存入lowcost相应位置 */
                adjvex[j] = k;/* 将下标为k的顶点存入adjvex */
            }
        }
    }
    cout << endl;
}

1、程序中1~16行是初始化操作,其中第7~8行 adjvex[0] = 0 意思是现在从顶点v0开始(事实上从那一点开始都无所谓,假定从v0开始),lowcost[0]= 0 表示v0已经被纳入到最小生成树中,之后凡是lowcost数组中的值被设为0就表示此下标的顶点被纳入最小生成树。

2、第11~15行表示读取邻接矩阵的第一行数据,所以 lowcost数组为{ 0 ,10, 65535, 65535, 65535, 11, 65535, 65535, 65535 },而adjvex数组为全0。至此初始化完毕。

3、第17~49行共循环了8次,i从1一直累加到8,整个循环过程就是构造最小生成树的过程。

4、第24~33行,经过循环后min = 10, k = 1。注意26行的if 判断lowcost[j] != 0 表示已经是生成树的顶点则不参加最小权值的查找。

5、第35行,因k = 1, adjvex[1] = 0, 所以打印结果为(0, 1),表示v0 至 v1边为最小生成树的第一条边,如下图的第一个小图。

6、第36行,因k = 1 将lowcost[k] = 0 就是说顶点v1纳入到最小生成树中,此时lowcost数组为{ 0,0, 65535, 65535, 65535, 11, 65535, 65535, 65535 }

7、第38~47行,j 循环从1 到8, 因k = 1,查找邻接矩阵的第v1行的各个权值,与lowcost数组对应值比较,若更小则修改lowcost值,并将k值存入adjvex数组中。所以最终lowcost = { 0,0, 18, 65535, 65535, 11, 16, 65535, 12 }。 adjvex数组的值为 {0, 0, 1, 0, 0, 0, 1, 0, 1 }。这里的if判断也表示v0和v1已经是生成树的顶点不参与最小权值的比对了。

上面所述为第一次循环,对应下图i = 1的第一个小图,由于要用文字描述清楚整个流程比较繁琐,下面给出i为不同值一次循环下来后的生成树图示,所谓一图值千言,大家对着图示自己模拟地循环8次就能理解普里姆算法的思想了。

即最小生成树的边为:(0, 1), (0, 5), (1, 8), (8, 2), (1, 6), (6, 7), (7, 4), (7, 3)

最后再来总结一下普里姆算法的定义:

由算法代码中的循环嵌套可得知此算法的时间复杂度为O(n^2)。

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

洛谷P2678 跳石头

题目背景 一年一度的“跳石头”比赛又要开始了! 题目描述 这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终...

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

2-SAT速成

本文只做总结性说明 2-SAT 2-SAT是k-SAT问题的一种,k-SAT问题在k>=3时已经被证明是NP完全问题 2-SAT问题定义比较简单 有n个布尔变量...

2826
来自专栏算法channel

图算法|Prim算法求最小生成树

01 — 一个实际问题 要在n个城市之间铺设光缆,要求有2个: 这 n 个城市的任意两个之间都可以通信; 铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,...

8457
来自专栏hadoop学习笔记

HanLP 关键词提取算法分析详解

l 参考论文:《TextRank: Bringing Order into Texts》

1506
来自专栏锦小年的博客

复杂网络(1)--图论的基本理论

1 图论的基本概念 1.1 图(graph)及其分类 (1) 图的定义:图是由点集V={vi}以及V中元素无序对的集合E={ek}所构成的二元组,记为G=(...

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

【每日一题】1445: [蓝桥杯][历届试题]最大子阵

节日快乐,筒子们! 不过小编还是给大家准备了每日一题! 2333 题目描述 给定一个n*m的矩阵A,求A中的一个非空子矩阵,使这个子矩阵中的元素和最大。 其...

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

欧拉函数详解

欧拉函数 我们用 表示欧拉函数 定义: 表示对于整数n,小于等于n中与n互质的数的个数 性质 1. 为积性函数 证明: 此处证明需要用到下面计算方法1中的...

3114
来自专栏DannyHoo的专栏

iOS开发中使用算法之冒泡法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u010105969/article/details/...

1103
来自专栏每日一篇技术文章

OpengL ES _ 入门_02

顶点是啥? 顶点就是坐标位置,不管你是画直线,三角形,正方体,球体,以及3D游戏人物等,都需要顶点来确定其形状。 顶点坐标创建 1.记住顶点的坐标数据类型...

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

BZOJ4518: [Sdoi2016]征途(dp+斜率优化)

Description Pine开始了从S地到T地的征途。 从S地到T地的路可以划分成n段,相邻两段路的分界点设有休息站。 Pine计划用m天到达T地。除第m...

3878

扫码关注云+社区

领取腾讯云代金券