本文最后更新于 1163 天前，其中的信息可能已经有所发展或是发生改变。
代码语言：javascript复制#include <cstdio>
#include <cstring>
#define INF 1000000 //无穷大
#define MAXN 21 //顶点个数最大值
int n, m; //顶点个数、边数
int Edge[MAXN][MAXN]; //邻接矩阵
int lowcost[MAXN];
int nearvex[MAXN];
void prim( int u0 ) //从顶点u0出发执行普里姆算法
{
int i, j; //循环变量
int sumweight = 0; //生成树的权值
for( i=0; i<n; i ) //初始化lowcost数组和nearvex数组
{
lowcost[i] = Edge[u0][i]; nearvex[i] = u0;
}
nearvex[u0] = -1;
for( i=1; i<n; i )
{
int min = INF;
int v = -1;
for( j=0; j<n; j ) //在lowcost数组(nearvex[ ]值为-1的元素)找最小值
{
if( nearvex[j]!=-1 && lowcost[j]<min )
{ v = j; min = lowcost[j]; }
}
if( v!=-1 ) //v==-1，表示没找到权值最小的边
{
printf( "%d %d %dn", nearvex[v], v, lowcost[v] );
nearvex[v] = -1;
sumweight = lowcost[v];
for( j=0; j<n; j )
{
if( nearvex[j]!=-1 && Edge[v][j]<lowcost[j] )
{
lowcost[j] = Edge[v][j];
nearvex[j] = v;
}
}
}//end of if
}//end of for
printf( "weight of MST is %dn", sumweight );
}//end of prime
int main( )
{
int i, j; //循环变量
int u, v, w; //边的起点和终点及权值
scanf( "%d%d", &n, &m ); //读入顶点个数n和边数m
memset( Edge, 0, sizeof(Edge) );
for( i=0; i<m; i )
{
scanf( "%d%d%d", &u, &v, &w ); //读入边的起点和终点
Edge[u][v] = Edge[v][u] = w; //构造邻接矩阵
}
for( i=0; i<n; i ) //对邻接矩阵中其他元素值进行赋值
{
for( j=0; j<n; j )
{
if( i==j ) Edge[i][j] = 0;
else if( Edge[i][j]==0 ) Edge[i][j] = INF;
}
}
prim( 0 ); //从顶点1出发构造最小生成树
return 0;
}Post Views: 277
