数据结构与算法16：最小生成树普利姆prim算法

void prim(int g[N][], int n)
{
	int isSelected[N];
	int cost[N];
	int prevex[N];
	int edge[N][2];
	int lowestCost;
	int vex;

	// 初始化
	for (int i = 0; i < n; ++i)
	{
		isSelected[i] = 0;
		cost[i] = g[0][i];
		prevex[i] = 0;
	}
	isSelected[0] = 1;

	for (int i = 1; i < n; ++i) // 将n-1个点加入树中
	{
		lowestCost = INFINITE;
		for (j = 1; j < n; ++j)
		{
			if (cost[j] < lowestCost && isSelected[j] == 0)
			{
				vex = j;
				lowestCost = cost[j];
			}
		}
		isSelected[vex] = 1;
		edge[i][0] = prevex[vex];
		edge[i][1] = vex;

		// 刷新cost[]
		for (j = 1; j < n; ++j)
		{
			for (k = 0; k < n; ++k)
			{
				if (isSelected[j] == 0 && isSelected[k] == 1 && cost[j] > g[j][k])
				{
					cost[j] = g[j][k];
					prevex[j] = k;
				}
			}
		}
	}
}