【数据结构】求最小生成树的权值之和——Prim算法

题源： 北航14级6系数据结构课第四次作业

【问题描述】
已知含有n个顶点的带权连通无向图，采用邻接矩阵存储，邻接矩阵以三元组的形式给出，只给出不包括主对角线元素在内的下三角形部分的元素，且不包括不相邻的顶点对。求该连通图的最小生成树的权值

【输入形式】
第一行给出结点个数n和三元组的个数count，以下每行给出一个三元组，数之间用空格隔开。（注意这里顶点的序号是从1到n，而不是0到n-1，程序里要小心！）
【输出形式】
最小生成树的权值
【样例输入】
5 8
2 1 7
3 1 6
3 2 8
4 1 9
4 2 4
4 3 6
5 2 4
5 4 2
【样例输出】
18
【样例说明】
权值是正整数，可能很大，但不需要考虑整型溢出问题

【题解&心得】

这个算法就在数据结构书本254页有，基本上就是照抄书就可以了，然后的话要注意的是表达正无穷大的方法

#include<limits.h>

在上面的头文件中包含了很多的极限值

比方说如果是int,那么无穷大可以用INT_MAX来表示

同理,无穷小可以用INT_MIN

最先开始我是用-1表示两个顶点之间的没有边的，但是发现根据算法里面的判定条件，-1就变成了最短的那条边，结果输出来的值就变成了 -n+1

然后我用INT_MAX表示正无穷，输出就是对的了

再一次铭记晏海华老师的警言： 工欲善其事必先利其器！

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAXVNUM 50


int getLength ( int Graph[][MAXVNUM],int n );

int main()
{
    int numV; // number of vertex
    int numE; // numver of edge
    int Graph[MAXVNUM][MAXVNUM];
    int i,j;
    int a,b,c;
    int length;

    scanf("%d%d",&numV,&numE);

    //初始化,-1表示两个顶点之间没有边相连
    for( i = 0; i < numV; i++)
        for( j = 0; j < numV; j++) {
            Graph[i][j] = INT_MAX;
        }

    //构建图的邻接矩阵
    for( i = 0; i < numE; i++) {

        scanf("%d%d%d",&a,&b,&c);
        Graph[a-1][b-1] = c;
        Graph[b-1][a-1] = c;

    }

    length = getLength(Graph,numV);
    printf("%d",length);

    return 0;
}

//求最小生成树的带权路径长度
int getLength ( int Graph[][MAXVNUM],int n ) {

    int lowcost[n];
    int teend[n];
    int mincost;
    int length = 0;//带权路径长度
    int i,j,k;
    int temp;

    lowcost[0] = 0;

    for ( i = 0; i < n; i++) {
        teend[i] = 0;
        lowcost[i] = Graph[0][i];
    }

    for ( i = 1; i < n; i++ ) {

        mincost = INT_MAX;

        j = 1;

        while ( j < n ) {

            if ( lowcost[j] > 0 && mincost > lowcost[j] ) {

                mincost = lowcost[j];
                k = j;
            }

        j++;
        }

        temp = teend[k];
        length += Graph[k][temp];
        lowcost[k] = 0;

        for( j = 0; j < n; j++ ) {

            if( Graph[k][j] < lowcost[j] ) {
                lowcost[j] = Graph[k][j];
                teend[j] = k;
            }

        }

    }

    return length;

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!