Prim算法用于从图中查找最小生成树。Prim算法找到包括图的每个顶点的边的子集，使得边的权重之和可以最小化。
Prim算法从单个节点开始，并在每一步探索所有相邻节点的所有连接边缘。 选择了具有最小权重的边缘在图表中没有引起循环。
算法如下 -
第1步：选择一个起始顶点
第2步：重复第3步和第4步，直到有条纹顶点
第3步：选择连接树顶点和具有最小权重的边缘顶点的边`e`。
第4步：将选定的边和顶点添加到最小生成树`T`。
[循环结束]
第5步：退出
示例：
使用prim算法构造下图中给出的图的最小生成树。
解决方案
第1步：选择一个起始顶点B。
第2步：添加与A相邻的顶点，连接顶点的边用虚线表示。
第3步：选择所有权重最小的边缘，即BD并将其添加到MST。添加D的相邻顶点，即C和E。
第4步：选择所有权重最小的边缘，在这种情况下，边缘DE和CD是这样的边缘。 将它们添加到MST并探索C的相邻，即E和A。
第5步：选择具有最小重量的边缘，即CA。不能选择CE，因为它会导致图中的循环。
在第4步中产生的图形是上图中所示的图形的最小生成树。
MST的成本将按以下方式计算：
成本(MST)= 4 + 2 + 1 + 3 = 10 个单位。
C语言实现示例代码
#include <stdio.h>
#include <limits.h>
#define vertices 5
int minimum_key(int k[], int mst[])
{
int minimum = INT_MAX, min,i;
for (i = 0; i < vertices; i++)
if (mst[i] == 0 && k[i] < minimum )
minimum = k[i], min = i;
return min;
}
void prim(int g[vertices][vertices])
{
int parent[vertices];
int k[vertices];
int mst[vertices];
int i, count,u,v;
for (i = 0; i < vertices; i++)
k[i] = INT_MAX, mst[i] = 0;
k[0] = 0;
parent[0] = -1;
for (count = 0; count < vertices-1; count++)
{
u = minimum_key(k, mst);
mst[u] = 1;
for (v = 0; v < vertices; v++)
if (g[u][v] && mst[v] == 0 && g[u][v] < k[v])
parent[v] = u, k[v] = g[u][v];
}
for (i = 1; i < vertices; i++)
printf("%d %d %d \n", parent[i], i, g[i][parent[i]]);
}
void main()
{
int g[vertices][vertices] = {{3, 2, 1, 9, 0},
{5, 1, 2, 10, 4},
{0, 4, 1, 0, 9},
{8, 10, 0, 2, 10},
{1, 6, 8, 11, 0},
};
prim(g);
}
执行上面示例代码，得到以下结果 -
0 1 5
0 2 0
0 3 8
1 4 6
