#include
#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
if (lowcost[j] < min && lowcost[j] != 0)
{
min = lowcost[j];
minid = j;
}
}
cout<<"生成数边的起点、终点及权值分别为："<< mst[minid]+1<<" "<
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
for (j =i+1; j
cout<<"请输入结点"<
graph[i][j] = n;
graph[j][i] = n;
}
graph[i][i]=MAXCOST;
}
cost = Prim(graph, m);
cout<<"最小生成树的权值为："<
