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

数据结构与算法16：普利姆prim算法
    Prim算法是一个计算图的最小生成树的算法。图的最小生成树指的是一个图中去掉一些边，使得剩余的边仍然保持连通，包含全部的点，并且权值之合最小。经过这样的处理后得到的肯定是一颗树。
    Prim算法和Dijkstra算法有着很相似的地方。Prim算法的大概思想是，把点划分为两个集合S和V，先放任意一个点到S中（因为随便放哪个得到的结果都是一样的），然后寻找一条边，这条边满足一端在S中，一端在V中，且权值最小，找到后把它放到边集里，把所连接的点也放到S集合中。不断进行这样的操作，直到最后V成为空集。
    C语言代码。假设是无向图使用邻接矩阵存储。

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;
}
}
}
}
}