Prim算法求解最小生成树的算法

//Prim算法求解最小生成树
void Prim_MinTree(MGraph *G)
{
int min, i, j, k;
int adjvex[MAX_VERTEX_NUM]; //保存相关顶点下标
int lowcost[MAX_VERTEX_NUM];//保存相关顶点间边的权值
lowcost[0] = 0; //初始化边(0,0)权值为0，即v0加入生成树
//lowcost的值修改为0
//就表示该下标的顶点已加入生成树
adjvex[0] = 0; //选取顶点v0为起始顶点
for (i = 1; i < G->n; i++) //循环遍历除v0外的全部顶点
{
lowcost[i] = G->edges[0][i]; //将v0顶点与其邻接点边上的权值存入数组
adjvex[i] = 0; //adjvex[]初始化为顶点v0的编号0
}
for (i = 1; i < G->n; i++)
{
min = INF; //初始化最小权值为无穷大
j = 1;
k = 0;
while (j < G->n) //遍历全部顶点
{
if (lowcost[j] != 0 && lowcost[j] < min)
{
//如果权值w满足0<w<min
min = lowcost[j]; //则让当前权值成为最小值
k = j; //若边的权值修改，将对应顶点下标存入k
}
j++;
}
printf("(%d,%d)", adjvex[k], k); //打印当前顶点边中权值最小的边
lowcost[k] = 0; //将当前边中选中的边权值置为0
//表明该下标的顶点已加入生成树
for (j = 1; j < G->n; j++)
{
//依附顶点k的边权值小于此前尚未加入生成树的边的权值
if (lowcost[j] != 0 && G->edges[k][j] < lowcost[j])
{
//则用较小的权值替换lowcost[]中的权值
lowcost[j] = G->edges[k][j];
//并将adjvex[]中对应位置的元素修改为新的依附顶点
adjvex[j] = k;
}
}
}
}