Prim算法实现_桂平ppt
本文最后更新于 1163 天前，其中的信息可能已经有所发展或是发生改变。
#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=1; 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=1; 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 %d\n", nearvex[v], v, lowcost[v] );
nearvex[v] = -1;
sumweight += lowcost[v];
for( j=1; 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("%d",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=1; i<=m; i++ )
{
scanf( "%d%d%d", &u, &v, &w ); //读入边的起点和终点
Edge[u][v] = Edge[v][u] = w; //构造邻接矩阵
}
for( i=1; i<=n; i++ ) //对邻接矩阵中其他元素值进行赋值
{
for( j=1; j<=n; j++ )
{
if( i==j ) Edge[i][j] = 0;
else if( Edge[i][j]==0 ) Edge[i][j] = INF;
}
}
prim( 1 ); //从顶点1出发构造最小生成树
return 0;
}Post Views: 194
本文参与?腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019-4-21 2，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读