priml.cpp

这是一个小小的程序

#include <stdio.h>
#define MAX  1000
#define MAXNode 20

typedef struct
{
 int vexnum,arcnum;
 int arcs[MAXNode][MAXNode];
}MGraph;//用邻接矩阵存储


void CreateMGraph(MGraph *p)
{
  int i,j,n,m;
  int v1,v2,w;
  printf("请输入顶点个数:"); 
  scanf("%d",&n); 
  p->vexnum=n;
  printf("请输入边数:");
  scanf("%d",&m);
  p->arcnum=m;
  for(i=0;i<n;++i)
   for(j=0;j<n;++j)
    if(i==j)
     p->arcs[i][j]=0;
    else
     p->arcs[i][j]=MAX;//邻接矩阵初始化

 for(i=1;i<=m;i++)
 {
   printf("请输入第%d条边的顶点序号v（0<=v<=%d）及该边权值：",i,n);
   scanf("%d %d %d",&v1,&v2,&w);
   if(v1>=0&&v1<n&&v2>=0&&v2<n)
   {
	 p->arcs[v1][v2]=w;
  	 p->arcs[v2][v1]=w;
   }//if
 }//for
}


int prim(MGraph G,int v)
{//用prim算法从序号为v的顶点出发构造最小生成树
	//并返回权值和
	int i,j,k,min,c=0;
	int lowcost[MAXNode],closest[MAXNode];
	for(i=0;i<G.vexnum;++i)
	{//对每一个结点
		closest[i]=v;//初值最近点
		lowcost[i]=G.arcs[v][i];
	}
 
 for(i=0;i<G.vexnum-1;i++)
 {
	min=MAX;
	for(j=0;j<G.vexnum;++j)
	  //在余下的顶点中找出最近的那个，并用k记下其序号
	if(lowcost[j]!=0&&lowcost[j]<min)
	{
		min=lowcost[j];
		k=j;
	}

	printf("v%d-v%d\t%d\n",closest[k],k,min);
	c+=min;

	lowcost[k]=0;//将此点归并
	for(j=0;j<G.vexnum;++j)
	 if(G.arcs[k][j]!=0&&G.arcs[k][j]<lowcost[j])
	 {
		lowcost[j]=G.arcs[k][j];
		closest[j]=k;
	 }

 }
 return c;
}


/*int Kruskal(Graph G)
{//用Kruskal算法从序号为0的顶点出发构造最小生成树
	//并返回权值和
int i,j,min,c=0,k;
for(i=0;i<G.vexnum;i++)
{//对每一个结点
	min=MAX;
	for(j=0;j<G.vexnum;++j)
	{	if(i!=j&&G.arcs[i][j]<min)
			min=G.arcs[i][j];
			k=j;
	}
			G.arcs[k][i]=MAX;
			printf("v%d-v%d %d\n",i,k,min);
			c+=min;
	}
	return c;

}*/


void Prim()
{
 int cost;
 MGraph G;
 CreateMGraph(&G);
 printf("prim得的最小生成树为:\n");
 printf("边\t 权值\t\n");
 cost=prim(G,0);
 printf("Cost :   %d\n",cost);
}