myprim.c

一个用Prim算法求解图的最小生成树

#include "stdio.h"
# include <stdlib.h> 
#define INFINITY  10000
#define MAX_VERTEX_NUM 20

/*typedef struct ArcCell{//弧的定义
  int adj;
}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];*/


typedef struct{
 int  vex[MAX_VERTEX_NUM];//图的顶点
 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//存放图的二维数组
  int vexnum;//顶点的个数
}MGraph;

struct{
  int adjvex;
  int lowcost;
}closedge[MAX_VERTEX_NUM];

void crearG(MGraph *g,int n)
{
  int i,j;
  g->vexnum=n;
  //顶点用I表示
  for(i=0;i<n;i++)
  {
    g->vex[i]=i;//将顶点的值置为I
  }
  //初始化图
  for(i=0;i<n;i++)
	  for(j=0;j<n;j++)
	  {
		scanf("%d",&g->arcs[i][j]);
	    
	  }

}

void prim(MGraph *G,int u)
{
	//辅助数组初始化
  int k=u;
  int i,j,m;
  for(j=0;j<G->vexnum;++j)
  {
	  if(j!=k)
	  {
		  closedge[j].adjvex=u;
          closedge[j].lowcost=G->arcs[k][j];
		  //closedge[j]={u,G.arcs[k][j]};
	  }

  }
 closedge[k].lowcost=0;
 //继续向u中添加结点
	  for(i=0;i<(G->vexnum-1);++i)
	  {
		  //选出下一个加入u中的结点
	    int min=INFINITY;
		for(m=1;m<G->vexnum;++m)
		{
		  if((closedge[m].lowcost<min)&&(closedge[m].lowcost!=0))
		  {
			  min=closedge[m].lowcost;
			  k=m;
		  }
		}
		printf("%4d%4d\n",closedge[k].adjvex,G->vex[k]);
		//修改辅助数组
		closedge[k].lowcost=0;
		
		for(j=0;j<G->vexnum;++j)
		{
			if(G->arcs[k][j]<closedge[j].lowcost)
			
				//closedge[j]={G.vex[k],G.arcs[k][j];
			{
			closedge[j].adjvex=G->vex[k];
			closedge[j].lowcost=G->arcs[k][j];
			}
			
		}
	  }

}

main()
{
  int n,i,j;
   MGraph *g=(MGraph *)malloc(sizeof(MGraph));
  printf("请输入顶点的个数：");
  scanf("%d",&n);
  crearG(g,n);
  prim(g,0);
  getch();
}