Prim算法(二)之 C++详解(二)
= 0 && weights[j] < min)
{
min = weights[j];
k = j;
}
j++;
}
// 经过上面的处理后，在未被加入到最小生成树的顶点中，权值最小的顶点是第k个顶点。
// 将第k个顶点加入到最小生成树的结果数组中
prims[index++] = mVexs[k];
// 将"第k个顶点的权值"标记为0，意味着第k个顶点已经排序过了(或者说已经加入了最小树结果中)。
weights[k] = 0;
// 当第k个顶点被加入到最小生成树的结果数组中之后，更新其它顶点的权值。
for (j = 0 ; j < mVexNum; j++)
{
// 当第j个节点没有被处理，并且需要更新时才被更新。
if (weights[j] != 0 && mMatrix[k][j] < weights[j])
weights[j] = mMatrix[k][j];
}
}
// 计算最小生成树的权值
sum = 0;
for (i = 1; i < index; i++)
{
min = INF;
// 获取prims[i]在mMatrix中的位置
n = getPosition(prims[i]);
// 在vexs[0...i]中，找出到j的权值最小的顶点。
for (j = 0; j < i; j++)
{
m = getPosition(prims[j]);
if (mMatrix[m][n]
min = mMatrix[m][n];
}
sum += min;
}
// 打印最小生成树
cout << "PRIM(" << mVexs[start] << ")=" << sum << ": ";
for (i = 0; i < index; i++)
cout << prims[i] << " ";
cout << endl;
}