图求最小生成树.txt

图求最小生成树的程序 功能良好 性能较好

图求最小生成树



#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
static int vertexcount= 0;
static int edgecount =0;
struct VERTEX 
{
	char vertex[3];
	bool key;
};
static VERTEX * Ve=NULL;
struct EDGE
{
	char edge[3];
	int GRI;
	bool key;
	VERTEX * Vertex1;
	VERTEX * Vertex2;
};
static EDGE *Ed=NULL;
VERTEX * GetVertex(char vertex[])
{
	for(int i=1;i<=vertexcount;i++)
	{
		if(strcmp(vertex,Ve[i-1].vertex)==0) return (Ve+i-1);
	}	
}
void BuildGraph()
{
	char vertex[3];
	cout<<"请输入你要建立图的顶点个数："<<flush;
	cin>>vertexcount;
	Ve=new VERTEX[vertexcount];
	cout<<"请分别输入"<<vertexcount<<"个顶点"<<endl;
	for(int i=1;i<=vertexcount;i++)
	{
		cin>>Ve[i-1].vertex;Ve[i-1].key=false;
	}
	cout<<"顶点输入完毕！"<<endl;
	cout<<"请输入你要建立图的边的条数:"<<flush;
	cin>>edgecount;
	Ed=new EDGE[edgecount];
	for(i=1;i<=edgecount;i++)
	{
		cout<<"请输入"<<i<<"条边的名称，权和两个关联顶点："<<flush;
		cin>>Ed[i-1].edge;cin>>Ed[i-1].GRI;
		cin>>vertex;
		Ed[i-1].Vertex1=GetVertex(vertex);
		cin>>vertex;
		Ed[i-1].Vertex2=GetVertex(vertex);
	}
	cout<<"边输入完毕！"<<endl;
}
EDGE * GetMin()
{
	EDGE * d=Ed;EDGE * ad=NULL;
	for(int i=1;i<=edgecount;i++)
	{
		if(d->key&&(d->Vertex1->key||d->Vertex2->key))
		{
			if(!ad) ad=d;
			if(ad->GRI>d->GRI) ad=d;
		}
		d++;
	}
	ad->key=false;
	ad->Vertex1->key?ad->Vertex2->key=true:ad->Vertex1->key=true;
	return ad;
}
void GetTree()
{
	VERTEX * p;
	EDGE * d;
	char vertex[3];
	cout<<"确定你要从哪个顶点开始建树："<<flush;
	cin>>vertex;
	p=GetVertex(vertex);
	p->key=true;
	cout<<"以下是最小生成树的边："<<endl;
	for(int i=1;i<vertexcount;i++)
	{
		d=GetMin();
		cout<<d->edge<<" , "<<flush;
	}
	
	delete []Ve;
	delete []Ed;
}
int main()
{

	BuildGraph();GetTree();
	return 0;
}