Prim算法的C语言实现

普里姆算法(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中,用记事本打开可以看到结果。这样方便调试。

坚持原创技术分享,您的支持将鼓励我继续创作!