最小生成树.cpp

数据结构课程设计

#define INFINITY 10000
#define MAX_VERTEX_NUM 30
#define OK 1
#define ERROR 0
#include<stdio.h>
#include<iostream.h>
typedef struct ArcCell
{
	char adjvex1,adjvex2;
	int weight;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
	char vex[MAX_VERTEX_NUM];
	AdjMatrix arcs;
	int vexnum,arcnum;
}MGraph;
typedef struct 
	{
	    char adjvex;
	    int lowcost;
	}closedge[MAX_VERTEX_NUM];
int CreatUDN(MGraph &G)
{   int LocateVex(MGraph &G,char u);
	int i,j,k;
	char v1,v2;
	int w;
	cout<<"输入这个无向图的顶点个数及弧数"<<endl;
	cin>>G.vexnum>>G.arcnum;
    cout<<"输入顶点的字符"<<endl;
	for(i=0;i<G.vexnum;++i)
		cin>>G.vex[i];
	for(i=0;i<G.vexnum;i++)
		for(j=0;j<G.vexnum;j++)
		{
			G.arcs[i][j].adjvex1=G.vex[i];
			G.arcs[i][j].adjvex2=G.vex[j];
			G.arcs[i][j].weight=INFINITY ;
		}
	for(k=0;k<G.arcnum;k++)
	{   
        cout<<"输入两个顶点的字符及权值"<<endl;
		cin>>v1>>v2>>w;
		i=LocateVex(G,v1);
		j=LocateVex(G,v2);
		G.arcs[i][j].weight=w;	
		G.arcs[j][i].weight=w;
	}
return OK;
}
void MiniSpanTree_PRIM(MGraph &G,char u)
{   int minimum(closedge &close,MGraph &G);
    int LocateVex(MGraph &G,char u);
	int k,i,j;
    closedge  closedge;
	k=LocateVex(G,u);
	for(j=0;j<G.vexnum;++j)
		if(j!=k){closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j].weight;}
	closedge[k].lowcost=0;
	for(i=1;i<G.vexnum;++i)
	{
		k=minimum(closedge,G);
		cout<<closedge[k].adjvex<<":"<<G.vex[k]<<endl;
        closedge[k].lowcost=0;
	    for(j=0;j<G.vexnum;++j)
		{
		   if(G.arcs[k][j].weight<closedge[j].lowcost)
		   {
			   closedge[j].adjvex=G.vex[k];
		       closedge[j].lowcost=G.arcs[k][j].weight;
		  }
		}
	}
}
int minimum(closedge &close,MGraph &G)
{
	int i,val;
	i=0;
	while (i<G.vexnum)
	{
		if(close[i].lowcost>0){val=i;break;}
	    else i++;
	}
    for(i=0;i<MAX_VERTEX_NUM;i++)
	{
		if(close[i].lowcost>0)
		{
			if(close[i].lowcost<close[val].lowcost)
			{
				val=i;
			}
		}
	}
	return val;
}
int LocateVex(MGraph &G,char u)
{
	int i=0;
	while(i<G.vexnum)
	{
	 if(G.vex[i]==u)return i;
	 else i++;
	}
	return ERROR;
}
void main()
{
   MGraph G;
   char u;
   CreatUDN(G);
   cout<<"第一个顶点"<<endl;
   cin>>u;
   MiniSpanTree_PRIM(G,u);
}