加点法求最小生成树
建立两个数组closet和lowcost，用于记录V-U中顶点j到U中顶点的最小边。
对V-U中的一个顶点j，他的最小边对应U中的某个顶点用closet[j]保存，对应边权为lowcost[j]
lowcost[i]=0,i属于U，lowcost[i]不等于0，i属于V-U
void Prim(MatGraph g, int v)
{
int closet[MAXV];
int lowcost[MAXV];
int min;
int i, j, k;
for (i = 0; i < g.n; i++)
{
lowcost[i] = g.edges[v][i];
closet[i] = v;
}
for (i = 1; i < g.n; i++)
{
min = INF;
for (j = 0; j < g.n; j++)
{
if (lowcost[j] != 0 && lowcost[j] < min)
{
min = lowcost[j];
k = j;
}
}
lowcost[k] = 0;
printf("边(%d,%d)权为%d\n", closet[k], k, min);
for (j = 0; j < g.n; j++)
{
if (lowcost[j] != 0 && lowcost[j] > g.edges[k][j])
{
lowcost[j] = g.edges[k][j];
closet[j] = k;
}
}
}
}
测试数据
7
0 28 100 100 100 10 100
28 0 16 100 100 100 14
100 16 0 12 100 100 100
100 100 12 0 22 100 18
100 100 100 22 0 25 24
10 100 100 100 25 0 100
100 14 100 18 24 100 100
原文：https://www.cnblogs.com/KIROsola/p/11920475.html