普利姆算法
一：介绍：
（一）：原理介绍
Prim算法构造最小生成树过程如下图所示：
1、首先从图中任选一个顶点加入树T中，此时最小生成树T中就只含有一个顶点
2、然后选择与当前最小生成树T中顶点集合距离最近的顶点，并将该顶点和相应的边加入最小生成树T中，每次操作树T中的顶点数量和边都加一。
3、执行1，2两步，当图中的所有顶点都并入到T中，T就是最小生成树了。此时T中必有n-1条边
（二）：算法思路介绍
1、先初始化辅助数组，即从起始点到其他顶点的权值保存到数组中，并标志起始点
2、循环执行以下操作（循环次数为图中顶点的数量减一，因为起始点不算）
（1）、定位数组中权值最小的权值，从而找到对应的下一个要加入的顶点。
（2）、在辅助数组中将新加入的顶点的权值置为0（自己到自己的距离为0）
（3）、跟新辅助数组，在新加入定点之后，集合T中的顶点到其他顶点的最小距离会变化，所以跟新新加入的顶点到其他顶点的距离，如果比原来的小，则跟新，否则不跟新。
二：代码
（一）：结构
#ifndef DATASTRUCTURE_MST_H
#define DATASTRUCTURE_MST_H
#include <stdio.h>
#include "../Graph/Graph.h"
//#include "../Graph/Graph.c"
//生成树的类型定义
typedef struct {
VertexType adjvex; //较早加入当前集合T的顶点（权值最小边的起始点）
VRType lowcost; //以该顶点为起始点的边的权值
}Edge; //辅助数组
typedef Edge closeEdge[MAX_VERTEX_NUM]; //创建一个辅助数组，表示已经加入到T中集合的顶点到其他顶点的最近距离
//在辅助数组中找到权值最小的边的数组下标
int Minimum(MGraph G,closeEdge close);
//普里母算法
void MinSpanTree_Prim(MGraph G,VertexType v);
#endif //DATASTRUCTURE_MST_H
（二）：算法
#include "MST.h"
/**
* 普利姆算法
* @param G 无向网
* @param v 开始顶点（随意） 初始为顶点1
*/
void MinSpanTree_Prim(MGraph G,VertexType v){
int k = LocateVex(G,v);
closeEdge close; //辅助数组
//初始化辅助数组，将与该起始点有关的所有边的信息：边的起始点和权值，初始化到辅助数组中
//如初始顶点为1，那么有顶点1相连的有顶点2，3，4，则顶点1到2，3，4为其边上的权值，而与顶点5，6不相邻，所以为INFINITY
//其中辅助数组的大小为图中顶点的数量，因此对应起始点与图中顶点的权值，即close[i].adjvex表示的是起始顶点，i对应的是顶点在
//G中顶点数组的下标，所以可以通过i来找到顶点值
for (int i = 0; i < G.vexnum; ++i) {
if (i!=k){
close[i].adjvex = k;
close[i].lowcost = G.arcs[k][i].adj;
}
}
//因为起始点已经在最小生成树中了，所以需要将其辅助数组置0，或者因为从该点开始的，所以距离为0
close[k].lowcost = 0;
//选择下一个点，并更新辅助数组中的信息
for (int i = 1; i < G.vexnum; ++i) { //为什么从1开始，因为目前已经有一个在最小生成树中了
k = Minimum(G,close); //找到权值最小的边所在数组的下标
printf("v%d \t v%d\t",G.vexs[close[k].adjvex],G.vexs[k]); //输出选择的路径
close[k].lowcost = 0; //入树之后需要将权值设置为0
//因为加入了一个顶点，那么辅助数组中的权值可能就会发生改变，所以，需要从新加入的顶点开始，比较其到其他邻接顶点的权值
//如果小的就需要更新
for (int j = 0; j < G.vexnum; ++j) {
if (G.arcs[k][j].adj<close[j].lowcost){
close[j].lowcost = G.arcs[k][j].adj;
close[j].adjvex = k;
}
}
printf("\n");
}
}
//在辅助数组中找到权值最小的边的数组下标
int Minimum(MGraph G,closeEdge close){
int min = INFINITY; //为无向网，所以INFINTIY表示最大距离
int index;
for (int i = 0; i < G.vexnum; ++i) {
if (close[i].lowcost>0&&close[i].lowcost<min){ //当权值为0的时候，说明顶点已经归到了最下生成树中了
min = close[i].lowcost;
index = i;
}
}
return index;
}
/**
* 确定顶点v在图中的位置
* @param G
* @param v 为顶点值
* @return 如果在图的顶点数组中找到，则返回在数组中的下标，否则返回-1；
*/
int LocateVex(MGraph G,VertexType v){
for (int i = 0; i < G.vexnum; ++i) {
if (v == G.vexs[i]){
return i;
}
}
return -1;
}