c语言实现最小生成树的普里姆算法（《数据结构》算法7.9）

无向网的最小生成树的普里姆算法是对点进行操作，先把图中的所有点分成两个集合，U（已经加入最小生成树的点），V-U（还未加入最小生成树的点）。先再U中加入一个最小生成树的起点u，然后用一个辅助数组closedge[i]记录从U到V-U中每个点的最小权值。注意：每次新加入一个点到U时，要重新对辅助数组进行赋值。算法的时间复杂度与顶点数量有关，是O(n^2)。所以常对顶点数量少，边数量多的稠密图使用。

下面代码：

#include<stdio.h>
#define MAX_VERTEX_NUM 100
#define MAX 1e10
typedef struct{
	int vexs[MAX_VERTEX_NUM];
	int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
	int vexnum,arcnum;
}MGraph;
struct{
	int adjvex;
	int lowcost;
}closedge[MAX_VERTEX_NUM];
bool inU[MAX_VERTEX_NUM]; //如果值为1表示vex【i】顶点在U中 
int LocateVex(MGraph G,int v){//返回顶点在图中的位置 
	for(int i=0;i<G.vexnum;i++){
		if(G.vexs[i]==v)return i;
	}
}
void CreateUDN(MGraph &G){//构造无向网的邻接矩阵 
	int i,j,k,v1,v2,weight;
	printf("分别输入顶点个数和边的个数：\n"); 
	scanf("%d%d",&G.vexnum,&G.arcnum);
	printf("输入各个顶点:\n");
	for(i=0;i<G.vexnum;i++)
	scanf("%d",&G.vexs[i]);
	
	for(i=0;i<G.vexnum;i++)
	 for(j=0;j<G.vexnum;j++)
	  G.arcs[i][j]=MAX;//初始化图，如果两点不通则把值赋为MAX 
	  
	printf("分别输入各条边的两个顶点和边的权值：\n");
	for(k=0;k<G.arcnum;k++){
		scanf("%d%d%d",&v1,&v2,&weight);
		i=LocateVex(G,v1);j=LocateVex(G,v2);
		G.arcs[i][j]=weight; 
		G.arcs[j][i]=weight;
	}
}
int minmum(MGraph G){//返回low_cost最小的 
	int min_cost=MAX;
	int temp;
	for(int i=0;i<G.vexnum;i++)
		if(closedge[i].lowcost<min_cost&&closedge[i].lowcost!=0&&inU[LocateVex(G,closedge[i].adjvex)]){
			min_cost=closedge[i].lowcost;temp=i;
		}	
	return temp;
}
void MiniSpanTree_PRIM(MGraph G,int u){//找到最小生成树的边并输出 
	int i,j,k;
	k=LocateVex(G,u);
	inU[k]=1;// 表示把vex[k]加入到U集合中 
	for(j=0;j<G.vexnum;j++)//初始化，即有一个顶点时U集 到V-U集的最小权值 
	if(j!=k){
		closedge[j].adjvex=u;
		closedge[j].lowcost=G.arcs[k][j];
	}
	closedge[k].lowcost=0;
	printf("最小生成树的边为：\n"); 
	for(i=1;i<G.vexnum;i++){//U集总共还要加入vexnum-1个顶点 
		k=minmum(G);//当前U到 V-U集最小的一个权值为closedge[k].lowcost
		inU[k]=1; //将vex[k]加入U集合 
	printf("%d %d\n",closedge[k].adjvex,G.vexs[k]);
	closedge[k].lowcost=0; 
	for(j=0;j<G.vexnum;j++){//当有新的顶点加入U集时，每个顶点到V-U集的lowcost都要重新赋值 
		if(G.arcs[k][j]<closedge[j].lowcost)//如果新的顶点到j的权值小与未加入新顶点之前的lowcost，则重新赋值 
		{closedge[j].adjvex=G.vexs[k];
		closedge[j].lowcost=G.arcs[k][j];}
	}
	}
}
int main(){
	MGraph G;
	CreateUDN(G);
	int u;//最小生成树的起点为u 
	printf("输入生成树的出发点：\n");
	scanf("%d",&u);
	MiniSpanTree_PRIM(G,u);
	return 0;
}