dit.cpp

最小生成树Prim算法的实现

#include<stdio.h>   
#include<stdlib.h>   
#include<string.h>   
#define   MAX_NAME   5   
#define   MAX_VERTEX_NUM   20     
typedef   char   Vertex[MAX_NAME];/*顶点名字串*/   
typedef   int   AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/   
struct   MGraph/*定义图*/   
{   
    Vertex   vexs[MAX_VERTEX_NUM];     
    AdjMatrix   arcs;     
    int   vexnum,arcnum;     
};   

typedef   struct   
{     
	Vertex   adjvex;   /*当前点*/   
	int   lowcost;         /*代价*/   
}minside[MAX_VERTEX_NUM];   

int   LocateVex(MGraph   G,Vertex   u)//定位   
{     
	int   i;   
	for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vexs[i])==0)return   i;   
	return   -1;   
}   

void   CreateGraph(MGraph   &G)   
{   
	int   i,j,k,w;   
	Vertex   va,vb;   
	printf("请输入无向网G的顶点数和边数(以空格为分隔)\n");   
	scanf("%d   %d",&G.vexnum,&G.arcnum);   
	printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);   
	for(i=0;i<G.vexnum;++i)   /*   构造顶点集*/   
		scanf("%s",G.vexs[i]);   
	for(i=0;i<G.vexnum;++i)   /*初始化邻接矩阵*/   
		for(j=0;j<G.vexnum;++j)   
			G.arcs[i][j]=0x7fffffff;     
		printf("请输入%d条边的顶点1   顶点2   权值(以空格作为间隔):   \n",G.arcnum);   
		for(k=0;k<G.arcnum;++k)   
		{   
			scanf("%s%s%d%*c",va,vb,&w);     
			i=LocateVex(G,va);   
			j=LocateVex(G,vb);   
			G.arcs[i][j]=G.arcs[j][i]=w;   /*对称*/   
		}   
}   

int   minimum(minside   SZ,MGraph   G)   
{   
	int   i=0,j,k,min;   
	while(!SZ[i].lowcost)i++;   
	min=SZ[i].lowcost;     
	k=i;   
	for(j=i+1;j<G.vexnum;j++)   
		if(SZ[j].lowcost>0&&min>SZ[j].lowcost)     
		{   
			min=SZ[j].lowcost;   
			k=j;   
		}   
		return   k;   
}   

void   MiniSpanTree_PRIM(MGraph   G,Vertex   u)   
{     
	int   i,j,k;   
	minside   closedge;   
	k=LocateVex(G,u);   
	for(j=0;j<G.vexnum;++j)     
	{   
		strcpy(closedge[j].adjvex,u);   
		closedge[j].lowcost=G.arcs[k][j];   
	}   
	closedge[k].lowcost=0;     
	printf("最小代价生成树的各条边为:\n");   
	for(i=1;i<G.vexnum;++i)   
	{     
		k=minimum(closedge,G);     
		printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]);     
		closedge[k].lowcost=0;     
		for(j=0;j<G.vexnum;++j)   
			if(G.arcs[k][j]<closedge[j].lowcost)   
			{     
				strcpy(closedge[j].adjvex,G.vexs[k]);   
				closedge[j].lowcost=G.arcs[k][j];   
			}   
	}   
}   

int   main()   
{   
	MGraph   g;   
	CreateGraph(g);     
	MiniSpanTree_PRIM(g,g.vexs[0]);     
	system("PAUSE");   
	return   0;   
}