MST（Minimum Spanning Tree，最小生成树）问题有两种通用的解法，Prim算法就是其中之一，它是从点的方面考虑构建一颗MST，大致思想是：设图G顶点集合为U，首先任意选择图G中的一点作为起始点a，将该点加入集合V，再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小，此时将b点也加入集合V；以此类推，现在的集合V={a，b}，再从集合U-V中找到另一点c使得点c到V中任意一点的权值最小，此时将c点加入集合V，直至所有顶点全部被加入V，此时就构建出了一颗MST。因为有N个顶点，所以该MST就有N-1条边，每一次向集合V中加入一个点，就意味着找到一条MST的边。
原文链接：https://blog.csdn.net/yeruby/article/details/38615045
下面用图和代码来解释：
我们首先定义一个数组：lowcost[i];我们初始将V1作为起点,那么lowcost[2] = 6,lowcost[3] = 1,lowcost[4] = 5,lowcost[5] = inf,lowcost[6] = inf;(其中inf=0x7ffffff，i指的是以i为终点的路径的长度，若没有一步可达的路径那么就赋值为inf)
我们明显可以看出，以V3为终点的路径最短那么就将V3加入集合V中，lowcost[2]=5，lowcost[3]=0，lowcost[4]=5，lowcost[5]=6，lowcost[6]=4，
将lowcost[3]标记为0，说明V3已经加入到集合V中了。 同时在这里更新以V3为起点所能直接到达的点的最短路。
此时，因为点V6的加入，需要更新lowcost数组
lowcost[2]=5，lowcost[3]=0，lowcost[4]=2，lowcost[5]=6，lowcost[6]=0
明显看出，以V4为终点的边的权值最小=2
此时，因为点V4的加入，需要更新lowcost数组：
lowcost[2]=5，lowcost[3]=0，lowcost[4]=0，lowcost[5]=6，lowcost[6]=0
重复执行直到所有点都加入集合V；
#include <iostream>
#define Max 100
#define MaxCost 0x7fffffff
using namespace std;
int Graph[Max][Max];
void prime(int n) {
int lowcost[Max];
;
int i, j, min1, minid, sum = 0;
for (i = 2; i <= n; i++) {
lowcost[i] = Graph[1][i];
}
mst[1] = 0;
for (i = 2; i <= n; i++) {
min1 = MaxCost;
minid = 0;
for (j = 2; j <= n; j++) {
if (lowcost[j] < min1 && lowcost[j] != 0) {
min1 = lowcost[j];
}
}
sum += min1;
lowcost[minid] = 0;
for (j = 2; j <= n; j++) {
if (Graph[minid][j] < lowcost[j]) {
lowcost[j] = Graph[minid][j];
}
}
}
cout << sum;
}
int main() {
ios::sync_with_stdio(false);
int n, m;//n为顶点的个数，m为边；
int i, j;
cin >> n >> m;
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
Graph[i][j] = MaxCost;
}
}
int b, e, cost;
for (i = 1; i <= m; i++) {
cin >> b >> e >> cost;
Graph[b][e] = cost;
Graph[e][b] = cost;
}
prime(n);
return 0;
}
原文：https://www.cnblogs.com/speedsnail/p/11514741.html