本文共 2174 字，大约阅读时间需要 7 分钟。

lowcost[0] = 0;//表示V0已经加入最小生成树，之后凡是lowcost数组中的值被置为0就表示此下标的顶点被纳入最小生成树for (int i = 1; i < G.numVEXS; i++) {   	lowcost[i] = G.arc[0][i];//lowcost剩下的部分用邻接矩阵第零行补满}int lowcost_belong[MAXVEX] = {    0 };

int lowcost_belong[MAXVEX] = { 0 };表示最初lowcost中的所有权值都来自V0。

理解算法之后，完整代码如下（n-1条边，所以循环次数为n-1）：

#include
   
    using namespace std;#define MAXVEX 15#define INFINITY 65536typedef struct {   	char vexs[MAXVEX];//顶点表	int arc[MAXVEX][MAXVEX];//邻接矩阵	int numVEXS;//顶点个数}MGraph;void MinispanTree_Prim(MGraph& G);int main() {   	MGraph G;	G.numVEXS = 9;	for (int i = 0; i < G.numVEXS; i++)		for (int j = 0; j < G.numVEXS; j++)		{   			if (i == j)				G.arc[i][j] = 0;			G.arc[i][j] = INFINITY;		}	G.arc[0][1] = 10; G.arc[0][5] = 11;	G.arc[1][0] = 10; G.arc[1][2] = 18; G.arc[1][6] = 16; G.arc[1][8] = 12;	G.arc[2][3] = 22; G.arc[2][8] = 8;	G.arc[3][2] = 22; G.arc[3][4] = 20; G.arc[3][7] = 16; G.arc[3][8] = 21;	G.arc[4][3] = 20; G.arc[4][5] = 26; G.arc[4][7] = 7;	G.arc[5][0] = 11; G.arc[5][4] = 26; G.arc[5][6] = 17;	G.arc[6][1] = 16; G.arc[6][5] = 17; G.arc[6][7] = 19;	G.arc[7][3] = 16; G.arc[7][4] = 7; G.arc[7][6] = 19;	G.arc[8][1] = 12; G.arc[8][2] = 8; G.arc[8][3] = 21;	MinispanTree_Prim(G);	system("pause");	return 0;}void MinispanTree_Prim(MGraph& G) {   	//initial	int min;	int k;	int lowcost[MAXVEX];	int lowcost_belong[MAXVEX] = {    0 };	lowcost[0] = 0;//表示V0已经加入最小生成树，之后凡是lowcost数组中的值被置为0就表示此下标的顶点被纳入最小生成树	for (int i = 1; i < G.numVEXS; i++) {   		lowcost[i] = G.arc[0][i];//lowcost剩下的部分用邻接矩阵第零行补满	}	//start	for (int i = 0; i < G.numVEXS-1; i++) {   //n-1条边		min = INFINITY;		for (int j = 0; j < G.numVEXS; j++)//这个循环用来找出lowcost中的min		{   			if (lowcost[j] != 0 && lowcost[j] < min)			{   				min = lowcost[j];				k = j;//k用来记录min的下标			}		}		cout << lowcost_belong[k] << "-->" << k << endl;		lowcost[k] = 0;		for (int j = 0; j < G.numVEXS; j++) //这个循环用来刷新lowcost和lowcost_belong		{   			if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j])//lowcost[j] != 0是为了排除已经纳入最小生成树的结点			{   				lowcost[j] = G.arc[k][j];				lowcost_belong[j] = k;			}		}	}}