android开发分享Prim计算最小生成树权值 C语言

题目描述

现在，你被委托在一个广阔区域里面为某些确定的结点设计连接网络。首先，你会给定在区域里面的一系列结点，和连接这些结点的一组线路。对于每条可能使用的线路，你能得到铺设该线路所需要的线缆长度。需要注意的是，在两个给定的结点之间可能存在许多路径。另外，假设给定的线路必定会连接（直接或间接）该区域里面的2个结点。

你的任务是为该区域设计一个网络，使得该区域中的任意2个结点之间都存在（直接或间接的）连接（也就是说，所有给定的结点之间都是连通的，但不一定存在直接相连的线路），同时，使得铺设该网络的线缆总长度最小。

输入格式

输入由多个测试构成。每个测试定义一个要求的网络。每个测试的第一个包含2个整数：第一个整数p给定区域内结点的数目，第二个整数r给出了线路的数目。接下来的r行，给出了两个结点之间的线路，每行包含3个整数：前2个数字表示线路连接的结点，第三个整数表示铺设该线路需要的线缆长度。每个整数之间用一个空格隔开。只给出一个整数p=0的测试表示输入结束。每个测试之间用一个空行隔开。

输入的最大的结点数目是50。给定的线路的最大长度是100。但是，可能存在的线路数目是无限的。给定的结点由整数1~p来标识（包含p）。需要注意，结点i和j之间的线路可能由i到j的线路来表示，也可能由j到i的线路来表示。

输出格式

对于每一个测试，在单独的一行输出一个数字，表示为铺设整个网络所需要的线缆总长度。

样例输入

1 0  2 3 1 2 37 2 1 17 1 2 68  3 7 1 2 19 2 3 11 3 1 7 1 3 5 2 3 89 3 1 91 1 2 32  5 7 1 2 5 2 3 7 2 4 8 4 5 11 3 5 10 1 5 6 4 2 12  0 

样例输出

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("0n");             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("%dn",prim(matrix,vnum,ednum)); 	} }