Prim计算最小生成树权值 C语言
题目描述
现在,你被委托在一个广阔区域里面为某些确定的结点设计连接网络。首先,你会给定在区域里面的一系列结点,和连接这些结点的一组线路。对于每条可能使用的线路,你能得到铺设该线路所需要的线缆长度。需要注意的是,在两个给定的结点之间可能存在许多路径。另外,假设给定的线路必定会连接(直接或间接)该区域里面的2个结点。
你的任务是为该区域设计一个网络,使得该区域中的任意2个结点之间都存在(直接或间接的)连接(也就是说,所有给定的结点之间都是连通的,但不一定存在直接相连的线路),同时,使得铺设该网络的线缆总长度最小。
输入格式
输入由多个测试构成。每个测试定义一个要求的网络。每个测试的第一个包含2个整数:第一个整数P给定区域内结点的数目,第二个整数R给出了线路的数目。接下来的R行,给出了两个结点之间的线路,每行包含3个整数:前2个数字表示线路连接的结点,第三个整数表示铺设该线路需要的线缆长度。每个整数之间用一个空格隔开。只给出一个整数P=0的测试表示输入结束。每个测试之间用一个空行隔开。
输入的最大的结点数目是50。给定的线路的最大长度是100。但是,可能存在的线路数目是无限的。给定的结点由整数1~P来标识(包含P)。需要注意,结点i和j之间的线路可能由i到j的线路来表示,也可能由j到i的线路来表示。
输出格式
对于每一个测试,在单独的一行输出一个数字,表示为铺设整个网络所需要的线缆总长度。
样例输入
2 37 17 68 2 19 11 7 5 89 91 32 2 5 7 8 11 10 6 12
样例输出
0 17 16 26
分析
即计算最小生成树的权值(相关知识:Prim算法和 Kruskal算法)
代码实现
#include <stdio.h> #define MAXVERTEX 52 #define MAXEDGE 102 #define INF 1e7 //prim算法计算最小生成树的权值 int Prim(int matrix[][MAXVERTEX],int vnum, int ednum){ int mst = 0; int isIntree[vnum+1] ; for(int i = 0; i < vnum+1; i++)isIntree[i] = 0; isIntree[1] = 1; //设置一个初始点 //遍历vnum-1次,找出vnum-1个点 for(int i = 0; i < vnum-1; i++){ int min = INF; int temp1,temp2; for(int j = 1; j <= vnum; j ++){ for(int k = j+1; k <= vnum; k ++){ if(isIntree[j]*isIntree[k] == 0 && isIntree[j]+isIntree[k] == 1 ){ if(matrix[j][k]<min){ min = matrix[j][k]; temp1 = j; temp2 = k; } } } } mst = mst + min; isIntree[temp1] = 1; isIntree[temp2] = 1; } return mst; } int main(){ //输入 int vnum; // 点数 int ednum; //边数 while(scanf("%d",&vnum)!=EOF){ scanf("%d",&ednum); if(vnum == 0)break; if( ednum == 0 ){ printf("0\n"); continue; } //矩阵初始化 int matrix[MAXVERTEX][MAXVERTEX] ; for(int i = 0; i <= vnum; i++){ for(int j = 0; j <= vnum; j++){ matrix[i][j] = INF; } } //输入边 边权 且 同一条边只保留最小边权 for(int i = 0; i < ednum; i++){ int v1,v2; int tempweight; scanf("%d",&v1); scanf("%d",&v2); scanf("%d",&tempweight); if(tempweight < matrix[v1][v2]){ matrix[v1][v2] = tempweight; matrix[v2][v1] = tempweight; } } //prim算法+输出 printf("%d\n",Prim(matrix,vnum,ednum)); } }
相关推荐
一颗有n个顶点的生成树有且仅有n-1条边,如果生成树中再添加一条边,则必定成环。此算法可以称为“加边法”,初始最小生成树边数为0,每迭代一次就选择一条满足条件的最小代价边,加入到最小生成树的边集合里。