最小生成树.cpp

最小生成树的算法,数据结构课程设计题目

//最小生成树
#include<stdio.h>



#define maxvertexnum 20
#define infinity 32768
typedef enum{DG,DN,UDG,UDN}GraphKind;

typedef struct ArcNode
{
	int adj;
}ArcNode;


typedef struct 
{
	char vertex[maxvertexnum];
	ArcNode arcs[maxvertexnum][maxvertexnum];
	int vexnum,arcnum;
	GraphKind DN;
}Adjmatrix;

Adjmatrix G;



typedef struct
{
	char adjvex;
	int lowcost;
}close;

close closedge[maxvertexnum];




//查找一个顶点在顶点数组中的位置函数
int locatevertex(Adjmatrix *G, char v)
{
	int j=0,k;
	for(k=0;k<G->vexnum;k++)
		if(G->vertex[k]==v)
		{
			j=k;
			break;
		}
		return(j);
		
}


//建立一个以邻接矩阵方式存储的图函数
void Create(Adjmatrix *G)
{
	int i,j,k,weight;
	char v1,v2; 
	printf("请输入图的顶点个数和边的条数：\n");       //请确认所输入的图为连通图
	scanf("%d%d",&(G->vexnum),&(G->arcnum));
	getchar();     
	
	for(i=0;i<G->vexnum;i++)
		for(j=0;j<G->vexnum;j++)
			G->arcs[i][j].adj=infinity;//初始化矩阵
		
		printf("输入图的所有顶点：\n");
		for(i=0;i<G->vexnum;i++) {
			scanf("%c",&G->vertex[i]);
			//	    	getchar();
		}
		getchar();
		printf("\n");
		
		
		printf("输出顶点元素：\n");
		for(i=0;i<G->vexnum;i++)//输出顶点数组
			printf("%c",G->vertex[i]);
		printf("\n");
		
		
		
		
		for(k=0;k<G->arcnum;k++)//建邻接矩阵
		{
			printf("输入一条弧的两个顶点以及权值:\n");
			scanf("%c%c%d",&v1,&v2,&weight); getchar();
			//	 printf("%c %c %d\n",v1,v2,weight);
			
			int m=locatevertex(G,v1);
			int n=locatevertex(G,v2);
			G->arcs[m][n].adj=weight;
		}
		
}



//求array[n].lowcost的最小正值，并返回他的序号
int Minium(close array[maxvertexnum]) 
{ 
   int i=0,j,k,min;
   while(!array[i].lowcost)
        i++;
   min=array[i].lowcost; //min为第一个不为0的值
   k=i;
   for(j=i+1;j<G.vexnum;j++)
     if(array[j].lowcost>0&&min>array[j].lowcost) //找到新的大于0的最小值 
     {
       min=array[j].lowcost;
       k=j;
     }
   return k;

}




//普利姆算法
void Minispantree(Adjmatrix gn,char u)
{
	
	int k=locatevertex(&gn,u);
	
	for(int j=0;j<gn.vexnum;++j) /* 辅助数组初始化 */
	{
		closedge[j].adjvex=u;
		closedge[j].lowcost=gn.arcs[k][j].adj;
	}
	
	
	closedge[k].lowcost=0;
	
	for(int i=0;i<gn.vexnum;i++)
		if(i!=k)
		{
			closedge[i].adjvex=u;
			closedge[i].lowcost=gn.arcs[k][i].adj;
		}
		
		
		for(int e=1;e<=gn.vexnum-1;e++)
		{
			int k0=Minium(closedge);
			int u0=closedge[k0].adjvex;
			int v0=gn.vertex[k0];
			printf("%c,%c\n",u0,v0);
			//		printf("%c,%c ",gn.vertex[u0],gn.vertex[v0]);//输出生成树的当前最小边
			closedge[k0].lowcost=0;
			
			for(i=0;i<gn.vexnum;i++)
				if(gn.arcs[k0][i].adj<closedge[i].lowcost)
				{
					closedge[i].lowcost=gn.arcs[k0][i].adj;
					closedge[i].adjvex=v0;
				}
		}
		
		
}


//主函数体
void main()
{
	Create(&G);
	printf("\n此图已经建成......\n");
//	char a;
	Minispantree(G,'a');
}