Prim算法
普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。
算法描述
1).输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
3).重复下列操作，直到Vnew = V：
a.在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；
4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。
算法图解
以该图为例若选择A点作为起始点，则于A相邻的有三条边，又因为AB之间的权值最小，所以讲B加入Vnew。
此时A，B点都已经在Vnew集合中，所以五条邻接边，选择相邻权值最小的点加入Vnew集合。
重复以上操作直到所有的点都被选入Vnew，则得出最小生成树。
最后得到最小生成树
算法设计
算法分两个部分
1、初始化
2、查找最小权值边并更新路径
void prim(int graph[][MAX], int n)
{
int Vnew[MAX]; //表示对应Dist的起点
int Dist[MAX]; //储存已选点和未选点之间的相邻边
int i, j, min, minid, sum = 0;
for (i = 2; i <= n; ++i) { //对几个数组进行初始化，因为默认从下标1开始，所以i=2
Vnew[i] = 1;
Dist[i] = graph[1][i]; //将顶点1的邻接边读入
}
Vnew[1] = 0;
for (i = 2; i <= n; i++) {//查找最小权值边并更新路径
min = MAXCOST;
minid = 0;
for (j = 2; j <= n; j++) {
if (min > Dist[j] && Dist[j] != 0) { //找出最小边和最小边对应的下标
min = Dist[j];
minid = j;
}
}
printf("%d--->%d : 权值为：%d\n", Vnew[minid], minid, min);
sum += min;
Dist[minid] = 0; //minid对应的最路路径为0
for (j = 2; j <= n; j++)
{
if (graph[minid][j] < Dist[j]) //对这一点直达的顶点进行路径更新 //若
{
Dist[j] = graph[minid][j];
Vnew[j] = minid;
}
}
}
printf("最小权值和为:%d", sum);
}
源码
https://github.com/Lu-ziyan/-/blob/master/prim.cpp