minispantree.cpp

最小生成树：分别输入顶点信息、边的信息

//MiniSpanTree的实现函数
#include "MiniSpanTree.h"


int CreatUDG(Graph &G)
{
	int flag=1;
	cout<<"There are two ways to creat Graph:\n"<<
		"F--Read information of Graph from CreatUDG file to creat Graph!\n"<<
		"I--Input information of Graph by hand to creat Graph!\n"<<endl;
	while(flag){
		switch(getchar()){
		case 'F':
			if(ReadFileToCreatUDG(G))
				cout<<"Succeed to creat Graph!\n"<<endl;
			else{
				cout<<"Fail to creat Graph!"<<endl;
				return ERROR;
			}
			flag=0;
			break;
		case 'I':
			if(ReadScreenToCreatUDG(G))
				cout<<"Succeed to creat Graph!\n"<<endl;
			else{
				cout<<"Fail to creat Graph!"<<endl;
				return ERROR;
			}
			flag=0;
			break;
		default:
			cout<<"Please input 'F' or 'I'!!!"<<endl;
			flag=1;
		}
	}
	return OK;
}
int ReadScreenToCreatUDG(Graph &G)
{
	FILE *fp;
	char vex1,vex2;
	int i,j;
	if((fp=fopen("CreateUDG","w+"))==NULL){
		cout<<"Fail to open CreateUDG file!"<<endl;
		return ERROR;
	}

	cout<<"Please input the number of node and arc!"<<endl;
	cout<<"Vexnum: ";
	cin>>G.vexnum;
	fprintf(fp,"%s %d\n","Vexnum:",G.vexnum);
	cout<<"Arcnum: ";
	cin>>G.arcnum;
	fprintf(fp,"%s %d\n","Arcnum:",G.arcnum);
	if((G.arcset_p=(ArcNode *)malloc(G.arcnum*sizeof(ArcNode)))==NULL)
		exit(OVERFLOW);
	if((G.vexset_p=(VexNode *)malloc(G.vexnum*sizeof(VexNode)))==NULL)
		exit(OVERFLOW);
	for(i=0;i<G.arcnum;i++)
		G.arcset_p[i].postag=i;

	cout<<"Please input the info of VexNode!"<<endl;
	fprintf(fp,"%s","Vertex_information:\n");
	for(i=0;i<G.vexnum;i++){//输入结点信息
		cout<<"Vertex["<<i+1<<"]:";
		cin>>G.vexset_p[i].data;
		fprintf(fp,"%c ",G.vexset_p[i].data);
	}

	cout<<"Over!\nPlease input the info of arc!"<<endl;
	fprintf(fp,"%s","\nArc_information:\n");
	for(i=0;i<G.arcnum;i++){//输入边的信息
		cout<<"Arc["<<i+1<<"]:";
		cin>>vex1>>vex2>>G.arcset_p[i].weight;
		if((G.arcset_p[i].vex1pos=Locate(G,vex1))==NONEXIST)
			return NONEXIST;
		if((G.arcset_p[i].vex2pos=Locate(G,vex2))==NONEXIST)
			return NONEXIST;
		fprintf(fp,"%c--%c %d\n",vex1,vex2,G.arcset_p[i].weight);
		for(j=0;j<i;j++){
			if(G.arcset_p[G.arcset_p[j].postag].weight>G.arcset_p[i].weight){
				G.arcset_p[i].postag=G.arcset_p[G.arcset_p[j].postag].postag;
				G.arcset_p[G.arcset_p[j].postag].postag++;
			}
		}
	}
	fclose(fp);
	return OK;
}

int ReadFileToCreatUDG(Graph &G)//从文件中读入建图
{
	char s[STRLEN],c;
	char vex1,vex2;
	int  i=0,j=0,postemp,temp;
	FILE *fp;
	if((fp=fopen("CreateUDG","r+"))==NULL){
		cout<<"Fail to open CreateUNG file!";
		return ERROR;
	}

	fscanf(fp,"%s %d",s,&G.vexnum);
	fprintf(stdout,"%s %d\n",s,G.vexnum);
	if((G.vexset_p=(VexNode *)malloc(G.vexnum*sizeof(VexNode)))==NULL)
		exit(OVERFLOW);
	fscanf(fp,"%s %d",s,&G.arcnum);
	fprintf(stdout,"%s %d\n",s,G.arcnum);
	if((G.arcset_p=(ArcNode *)malloc(G.arcnum*sizeof(ArcNode)))==NULL)
		exit(OVERFLOW);
	for(i=0;i<G.arcnum;i++)
		G.arcset_p[i].postag=i;

	//读顶点信息
	fscanf(fp,"%s",s);
	fprintf(stdout,"%s\n",s);
	c=0,fgetc(fp);
	for(i=0;c!='\n'&&i<G.vexnum;i++){
		G.vexset_p[i].data=fgetc(fp);
		c=fgetc(fp);
		fprintf(stdout,"%c ",G.vexset_p[i].data);
	}
	if(i<G.vexnum||c!='\n'&&c!=' '){
		cout<<"\nThe number of vertex set is equal to "<<G.vexnum<<endl;
		return ERROR;
	}
	

	//读边的信息
	fscanf(fp,"%s",s);
	fprintf(stdout,"\n%s\n",s);
	c=fgetc(fp);
	for(i=0;!feof(fp)&&i<G.arcnum;i++){
		fscanf(fp,"%c--%c %d\n",&vex1,&vex2,&G.arcset_p[i].weight);
		fprintf(stdout,"%c--%c %d\n",vex1,vex2,G.arcset_p[i].weight);
		G.arcset_p[i].vex1pos=Locate(G,vex1);
		G.arcset_p[i].vex2pos=Locate(G,vex2);
		postemp=i;
		for(j=0;j<i;j++){
			if(G.arcset_p[G.arcset_p[j].postag].weight>G.arcset_p[postemp].weight){
				temp=G.arcset_p[j].postag;
				G.arcset_p[j].postag=postemp;
				postemp=temp;
			}
		}
		G.arcset_p[i].postag=postemp;
	}
	fclose(fp);
	return OK;
	
}



int Locate(Graph G,char vex)
{
	int i;
	for(i=0;i<G.vexnum;i++){
		if(G.vexset_p[i].data==vex)
			break;
	}
	if(i>=G.vexnum)
		return NONEXIST;
	return i;
}

int Find_MFSet(MFSet S,int i)//找集合S中i所在的子集的根
{	
	int j;
	if(i<0||i>S.nodenum)
		return ERROR;
	for(j=i;S.parent[j]>0;j=S.parent[i]);
	return j;
}

int MixMFSet(MFSet &S,int i,int j)
{
	if(i<0||i>S.nodenum||j<0||j>S.nodenum)
		return ERROR;
	if(S.parent[i]>S.parent[j]){
		S.parent[j]+=S.parent[i];
		S.parent[i]=j;
	}
	else{
		S.parent[i]+=S.parent[j];
		S.parent[j]=i;
	}
	return OK;
}

int MinSpanTree(Graph G,MFSet &S)//生成最小生成树
{
	int root1,root2;
	int i,j;

	S.nsetptr=G.vexset_p;
	S.nodenum=G.vexnum;
	if((S.parent=(int *)malloc(S.nodenum*sizeof(int)))==NULL)
		exit(OVERFLOW);
	for(i=0;i<S.nodenum;i++)
		S.parent[i]=-1;

	for(i=0,j=1;i<G.arcnum&&j<=G.vexnum-1;i++){//边要等于n-1
		root1=Find_MFSet(S,G.arcset_p[G.arcset_p[i].postag].vex1pos);
		root2=Find_MFSet(S,G.arcset_p[G.arcset_p[i].postag].vex2pos);
		if(root1!=root2){
			MixMFSet(S,root1,root2);
			cout<<G.vexset_p[G.arcset_p[G.arcset_p[i].postag].vex1pos].data
				<<"----"
				<<G.vexset_p[G.arcset_p[G.arcset_p[i].postag].vex2pos].data<<endl;
			j++;
		}
	}
	return OK;
}



int main()
{
	Graph G;
	MFSet S;
	CreatUDG(G);
	MinSpanTree(G,S);
	return 0;
}