普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现；并在1957年由美国计算机科学家罗伯特·普里姆独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。

以上摘自维基百科。我简略地说下算法思想（或许不大严谨，想要看专业严谨版的朋友自行百度）：

1.在把生成树看成一个集合（开始集合为空，到各个结点的距离当然未知） 2.结点与集合之间的权值可以看成结点到集合距离 3.将第一个结点加入集合，并初始化集合与其他结点的距离 4.搜索集合与结点最小的权值（距离），并把这点加入集合 5.更新集合与结点之间的距离 6.不断重复4和5步，直到所有的结点都加入了集合 （实际上把一个结点加入集合的时候，可以记录这个结点的父节点，也就是前驱，这么说吧，当找到一个与集合最小的结点的时候，他与集合中哪一结点的距离最小，把他记录来，作为生成树的路径）

算法实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#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\n", 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;
            }
    }
}

输入样例：

1
2
3
4
5
6
7

6
0 7 6 2 0 0
7 0 0 3 4 0
6 0 0 5 0 3
2 3 5 0 5 4
0 4 0 5 0 6
0 0 3 4 6 0

输出样例：

1
2
3
4
5

2--->4
3--->6
4--->1
5--->2
6--->4

大家可以新建prim.txt把输入样例写进去，改名成prim.in，然后解除注释这两行：

1
2

freopen("prim.in", "r", stdin); //打开文件
freopen("prim.out", "w", stdout);

输出在prim.out中，用记事本打开可以看到结果。这样方便调试。