题源: 北航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; }