本文引用自泽爷工作室http://www.zeyes.org/study/clang/189.html
算法思想:
1.在把生成树看成一个集合（开始集合为空，到各个结点的距离当然未知） 2.结点与集合之间的权值可以看成结点到集合距离 3.将第一个结点加入集合，并初始化集合与其他结点的距离 4.搜索集合与结点最小的权值（距离），并把这点加入集合 5.更新集合与结点之间的距离 6.不断重复4和5步，直到所有的结点都加入了集合 （实际上把一个结点加入集合的时候，可以记录这个结点的父节点，也就是前驱，这么说吧，当找到一个与集合最小的结点的时候，他与集合中哪一结点的距离最小，把他记录来，作为生成树的路径）
算法实现:
#include <stdio.h>
#define MAXN 100
#define INF 100001 /*INF表示不存在边的长度，用一个很大的数表示它*/
void prim(int [][MAXN], int [], int); //函数原型
int main(void)
{
int i, j, t, n;
int w[MAXN][MAXN], fa[MAXN]; /*w是邻接矩阵，fa[x]表示是结点x的父结点）*/
//freopen("prim.in", "r", stdin); //打开文件
//freopen("prim.out", "w", stdout);
scanf("%d", &n);
for(i = 1; i <= n; i++) for(j = 1; j <= n; j++ )
{
scanf("%d", &t); //数据读入
w[i][j] = (t == 0) ? INF : t;
}
prim(w, fa, n); //调用函数
for(i = 2; i <= n; i++) //打印结果
printf("%d--->%d ", i, fa[i]);
return 0;
}
void prim(int w[][MAXN], int fa[], int n)
{
int i, j, m, k; int d[MAXN]; /*d[j]可以理解成结点j到生成树(集合)的距离，它的最终值是w[j][fa[j]]*/
for(j = 1; j <= n; j++)
{
d[j] = (j == 1 ? 0 : w[1][j]); /*将第一个结点加入集合，并初始化集合与其他结点的距离*/
fa[j] = 1; /*当前集合中有且只有一个结点1，其他结点暂时未加入集合，所以没有父结点，就先姑且初始化成1*/
}
for(i = 2; i <=n; i++)
{
m = INF;
for(j = 1; j <= n; j++)
if(d[j] <= m && d[j] != 0) m = d[k = j]; /*选取与集合距离最小的边*/
d[k] = 0; /*0在这里表示与集合没有距离，也就是说赋值0就是将结点k添加到集合中*/
for(j = 1; j <= n; j++) /*对刚加入的结点k进行扫描，更新d[j]的值*/
if(d[j] > w[k][j] && d[j] != 0)
{
d[j] = w[k][j];
fa[j] = k;
}
}
}