复制代码 代码如下:
#include <iostream.h>
#define MAX 100
#define MAXCOST 100000

int graph[MAX][MAX];

int Prim(int graph[MAX][MAX], int n)
{

int lowcost[MAX];


int mst[MAX];

int i, j, min, minid, sum = 0;


for (i = 1; i < n; i++)
{

lowcost[i] = graph[0][i];


mst[i] = 0;
}


lowcost[0] = 0;


for (i = 1; i < n; i++)
{
min = MAXCOST;
minid = 0;


for (j =1; j <n; j++)
{

if (lowcost[j] < min && lowcost[j] != 0)
{
min = lowcost[j];
minid = j;
}
}

cout<<"生成数边的起点、终点及权值分别为："<< mst[minid]+1<<" "<<minid+1<<" "<<min<<endl;

sum += min;


lowcost[minid] = 0;


for (j = 1; j < n; j++)
{

if (graph[minid][j] < lowcost[j])
{

lowcost[j] = graph[minid][j];


mst[j] = minid;
}
}
}

return sum;
}

void main()
{
int i, j, m,n;
int cost;

cout<<"请输入该图结点个数：";
cin>>m;

for (i = 0; i <m; i++)
{
for (j =i+1; j <m; j++)
{
cout<<"请输入结点"<<i+1<<"到结点"<<j+1<<"边的权值，若无边则输入MAXCOST(100000):";
cin>>n;
graph[i][j] = n;
graph[j][i] = n;
}
graph[i][i]=MAXCOST;
}


cost = Prim(graph, m);
cout<<"最小生成树的权值为："<<cost<<endl;
}