C语言实现Prim算法

• 话不多说，思想简单，直接上代码

维护两个数组。
一个lowcost数组，表示当前已经归入最小生成树的结点集合与未归入的集合节点之间的最小代价；
一个visited数组，表示是否已经归入最小生成树
每次从lowcost数组中找到未归入最小生成树但代价最小的节点，将之归入最小生成树，之后根据归入的新节点更新lowcost数组
直到所有节点全部归入最小生成树，算法结束；
下例用未压缩的邻接矩阵存储图

#define MAX_VEXNUM 100
typedef struct{
    int edge[MAX_VEXNUM][MAX_VEXNUM];
    int vex[MAX_VEXNUM];
    int vexmun,edgenum;
}MGraph;
void prim(MGraph G,int v0,int &sum){//从v0开始，返回总路径长sum
    int lowcaost[MAX_VEXNUM];//最小代价数组
    int visited[MAX_VEXNUM];//节点是否包含在最小生成树中
    for(int i=0;i