Prim求无向连通图最小生成树

Prim算法是一种从顶点开始扩展最小生成树的贪心算法,它的核心步骤如下:

初始化：向空树T=（VT，ET）中添加图G=（V，E）的任一顶点u0，使VT={u0}，ET=空集

循环（重复下列操作至VT=V）: 从图G中选择满足{（u，v）| u属于VT，v属于V-VT}且具有最小权值得边(u,v)，并置VT=VT U {v}，ET=ET U {（u，v）}

#include <stdio.h>#include <string.h>
#define VMAX 50
#define INF 0x7fffffff//2147483647

typedef struct{
	//	ElemType Vex[VMAX];//顶点表
	int Edge[VMAX][VMAX];//邻接矩阵
	int vexnum,arcnum;//当前顶点数和边数
}MGraph;

int prim(MGraph G)
{
	int dist[VMAX],mst[VMAX];//mst保存生成树的边在S中对应的顶点
	bool visited[VMAX];
	int result = 0,mins;
	int j = 3;//设置起始结点
	memset(visited,false,sizeof(visited));
	//初始化最短距离
	for(int i=1;i<=G.vexnum;i++)
		if(i!=j)
		{
			dist[i] = G.Edge[i][j];
			mst[i] = j;//生成树的边在S中对应的顶点初设为起始结点
		}
	visited[j] = true;
	//进行vexnum-1次顶点选择
	for(int r=1;r<G.vexnum;r++)
	{
		mins = INF;
		//从V-S中选择和S中顶点权值最小顶点进入S中
		for(int k=1;k<=G.vexnum;k++)
			if(!visited[k] && mins > dist[k])
			{	
				mins = dist[k];
				j = k;
			}
		printf("dist(%d,%d)=%d\n",mst[j],j,mins);
		result += mins;
		visited[j] = true;
		//并入顶点j后,更新V-S中顶点到S中顶点的最小权值
		for(int t=1;t<=G.vexnum;t++)
		{
			if(!visited[t] && G.Edge[j][t] < dist[t])
			{
				dist[t] = G.Edge[j][t];
				mst[t] = j;
			}
		}
	}
	return result;
}

int main()
{
	MGraph G;
	int vex1,vex2;
	printf("无向图顶点数、边数:");
	scanf("%d%d",&G.vexnum,&G.arcnum);
	//必须首先将Edge初始化为INF
	//memset(G.Edge,INF,sizeof(G.Edge)); //-1
	for(int r=1;r<=G.vexnum;r++)
		G.Edge[r][r] = INF;
	for(int t=1;t<=G.vexnum;t++)
		for(int k=t+1;k<=G.vexnum;k++)
			G.Edge[t][k] = G.Edge[k][t] = INF;
	printf("依次输入边结点及对应的权值:\n");
	for(int i=0;i<G.arcnum;i++)
	{
		scanf("%d%d",&vex1,&vex2);
		scanf("%d",&G.Edge[vex1][vex2]);
		G.Edge[vex2][vex1] = G.Edge[vex1][vex2];
	}
	printf("最小生成树如下:\n");
	printf("权值之和:%d\n",prim(G));
	return  0;
}