假设我们现在有一个连通图，顶点与顶点之间的边拥有权值，在保证所有顶点都在树中的情况下，使顶点之间的权值之和最小的树，就是最小生成树。
所谓普利姆算法，就是随便取一个点，然后根据已知边的权值大小，去寻找下一个顶点的过程。例如取 0 为起始的最小树。对于 0 来说，权值最小的边是 1，所以我们把顶点 2 也纳入到最小树，在这些已知边中，4 为权值最小的边（以访问的顶点不再访问），所以把顶点 5 纳入到最小树中。
依次类推，遵循的规则就是：
1.在已知边的权值中寻找最小权值的边，并把该节点纳入到最小树中。
2.因为是树结构，所以不能有回路，也就是不能访问已经访问过的顶点。
最后，最小树就是红色圈的边构成的树：
理解起来到没什么困难，但是代码比较抽象难理解。
首先要明确我们的第一步：随意传进去一个顶点，找到该顶点的最小权值边，并把该边连接的顶点纳入最小树。下面的代码是准备工作，vex_weight是传入顶点的边的权值，closest_set是离传入顶点最近的顶点。由于图已经创建完成，G->arcs其实就是array。
至于为什么让closest_set[i] = vex;是因为一开始最小生成树中只有传入的顶点没有其他顶点，后面也会讲到。
#define Max 999 表示两个顶点之间没有边相连，是断开的
int array[6][6] = {
0,6,1,5,Max,Max,
6,0,5,Max,3,Max,
1,5,0,5,6,4,
5,Max,5,0,Max,2,
Max,3,6,Max,0,6,
Max,Max,4,2,6,0
};
void Prim(Graph* G, int vex) {
int* vex_weight = (int*)malloc(sizeof(int) * G->vexsNum);
int* closest_set = (int*)malloc(sizeof(int) * G->vexsNum);
int node;
for (int i = 0; i < G->vexsNum; i++) {
vex_weight[i] = G->arcs[vex][i];
closest_set[i] = vex;
}我们可以先写出下面的代码，第一个for循环的意思是要找 顶点数-1 次顶点，因为传入顶点已经在树中了，第二个for循环是要找到与顶点连接，权值最小的另一个顶点，并且记录下这个顶点 node，把它的权值置为 0，（表示已经加入树，例如：顶点和自身之间的权值也为 0。）最后打印。
for (int a = 1; a < G->vexsNum; a++) {
int min = Max;
for (int b = 0; b < G->vexsNum; b++) {
if (vex_weight[b] != 0 && vex_weight[b] < min) {
min = vex_weight[b];
node = b;
}
}
vex_weight[node] = 0;
printf("%d -> %d ,weight = %d", closest_set[node], node, min);
printf("\n");
}看似没有什么问题，但是如果传入顶点和部分顶点不相连，该怎么更新我们传入顶点呢。在这里我们可以这样做：
假设我们传入的是 0 这个顶点，首先按照我们上面代码的逻辑，找到最小权值边的顶点，所以把和2 顶点的权值边置为 0，表示已经把 2 顶点纳入到树中，打印完毕。那么现在请问，下次寻找应该在那些权值边中寻找最小顶点，答案是 0 和 2 顶点，那么如何更新权值呢？
我们现在可以把 0 和 2 顶点看成是一个顶点，看似传入顶点和 4，5 顶点不相连，但是因为 2 顶点的存在，其实可以相连。因为 0 和 2 都在树中，我们的目的只是找到最小权值的顶点，所以更新如下：node是第一个最小权值顶点，也就是蓝色框。
for (int j = 0; j < G->vexsNum; j++) {
if (G->arcs[node][j] < vex_weight[j]) {
vex_weight[j] = G->arcs[node][j];
closest_set[j] = node;
}
}
更新过后，传入顶点的权值和刚纳入到最小树的权值相比较，更新权值。
那么closest_set[j] = node;是什么意思，为什么更新了最近顶点数组，这是因为，与传入顶点不相连的顶点，是通过某些顶点间接相连的。就拿刚才的例子来说，原来的最近顶点数组是这样的：
经过第一个顶点的纳入变成了：
变成 2 的位置正好对应刚才的更新权值的位置，也就是说，把 0 和 2 节点缝合了一下，把没用的较大权值删去。
接着解释，下一轮又开始权值最小的寻找，这时最小权值是 4 ，这时打印的就是 2 顶点到 5 顶点，而不是 0 顶点到 5 顶点，因为是因为纳入 2 顶点所以才和 5 顶点相连的，这就是更新顶点的作用。
我们只需要把更新代码放在打印的后面：
void Prim(Graph* G, int vex) {
int* vex_weight = (int*)malloc(sizeof(int) * G->vexsNum);
int* closest_set = (int*)malloc(sizeof(int) * G->vexsNum);
int node;
for (int i = 0; i < G->vexsNum; i++) {
vex_weight[i] = G->arcs[vex][i];
closest_set[i] = vex;
}
for (int a = 1; a < G->vexsNum; a++) {
int min = Max;
for (int b = 0; b < G->vexsNum; b++) {
if (vex_weight[b] != 0 && vex_weight[b] < min) {
min = vex_weight[b];
node = b;
}
}
vex_weight[node] = 0;
printf("%d -> %d ,weight = %d", closest_set[node], node, min);
printf("\n");
for (int j = 0; j < G->vexsNum; j++) {
if (G->arcs[node][j] < vex_weight[j]) {
vex_weight[j] = G->arcs[node][j];
closest_set[j] = node;
}
}
}
}
这就是文章的全部内容了，希望对你有所帮助，如有错误欢迎评论。
