design.cpp

图的算法实现 （1）将图的信息建立文件； （2）从文件读入图的信息

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <graphics.h>
#include <math.h>
#define PI 3.1415926
#define N 20
#define INFINITY 9999

typedef struct{
char vexs[N];
int arcs[N][N];
int vexnum,arcnum;
}MGraph;

typedef struct{
char adjvex;
int lowcost;
}close;
close closedge[N];

int locatevex(MGraph G,char m)
{
	int i;
	i=0;
	while(1)
	{
		if(G.vexs[i]==m)
			return i;
		else
			i++;
	}
}

MGraph Creat(char *xian1,char *xian2)
{
	MGraph G;
	int i,j,k,w;
	char m,n;
	FILE*fp;
	fp=fopen("aa22.txt","r");
	if(fp==NULL)
	{
		printf("The file cannot be open!");
		exit(0);
	}
	fscanf(fp,"%d",&G.vexnum);
	fgetc(fp);
	fscanf(fp,"%d",&G.arcnum);
	for(i=0;i<G.vexnum;i++)
	{
		fgetc(fp);
		G.vexs[i]=fgetc(fp);
	}
	G.vexs[G.vexnum]='\0';

	for(i=0;i<G.vexnum;i++)
	{
		for(j=0;j<G.vexnum;j++)
		{
		       G.arcs[i][j]=INFINITY;
		}
	}
	for(k=0;k<G.arcnum;k++)
	{
		fgetc(fp);
		m=fgetc(fp);
		xian1[k]=m;
		fgetc(fp);
		n=fgetc(fp);
		xian2[k]=n;
		fgetc(fp);
		fscanf(fp,"%d",&w);
		i=locatevex(G,m);
		j=locatevex(G,n);
		G.arcs[i][j]=w;
		G.arcs[j][i]=w;
	}
	fclose(fp);
	return(G);
}

void  num(int u,int &x,int &y,MGraph G)
{
	int rad=160,eg;
	double p,enda;
	p=360/G.vexnum;
	eg=p*u;
	enda=eg*PI/180;
	x=300+cos(enda)*rad;
	y=220-sin(enda)*rad;

}


int minimun(close closedge[N],int n)
{
	int i,k,a,j;
	for(i=0;closedge[i].lowcost==0;i++);
	a=closedge[i].lowcost;
	k=i;
	for(j=i+1;j<n;j++)
	{
		if(a>closedge[j].lowcost&&closedge[j].lowcost!=0)
		{
			a=closedge[j].lowcost;
			k=j;
		}
	}
	return k;
}

void MiniSpanTree_PRIM(MGraph G,char u,char *str1,char *str2)
{
	int k,i,j;
	int s=0,t=0;
	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];
		}
	}
	closedge[k].lowcost=0;
	for(i=1;i<G.vexnum;i++)
	{
		k=minimun(closedge,G.vexnum);
		str1[s++]=closedge[k].adjvex;
		str2[t++]=G.vexs[k];
		closedge[k].lowcost=0;
		for(j=0;j<G.vexnum;j++)
		{
			if(G.arcs[k][j]<closedge[j].lowcost)
			{
				closedge[j].adjvex=G.vexs[k];
				closedge[j].lowcost=G.arcs[k][j];
			}
		}
	}
}

void draw(char *xian1,char *xian2,int h,MGraph G,int color,int width,int zi)
{
	int i,m,n;
	int x1,y1,x2,y2;
	char s1[5],s2[5];
	for(i=0;i<h;i++)
	{
		setcolor(color);
		setlinestyle(0,0,width);
		m=locatevex(G,xian1[i]);
		n=locatevex(G,xian2[i]);
		num(m,x1,y1,G);
		num(n,x2,y2,G);
		line(x1,y1,x2,y2);
		circle(x1,y1,2);
		if(zi==0)
		{	sprintf(s1,"%c",xian1[i]);
			setcolor(WHITE);
			settextstyle(8,0,2);
			outtextxy(x1+10,y1-10,s1);
		}
		moveto(x2,y2);
		circle(x2,y2,2);
		if(zi==0)
		{
			sprintf(s2,"%c",xian2[i]);
			outtextxy(x2+10,y2-10,s2);
		}
	}
}

void output(MGraph G)
{
	int i,j,x1,y1,x2,y2;
	char str[5];
	for(i=0;i<G.vexnum;i++)
	{
		for(j=0;j<G.vexnum;j++)
		{
			if(G.arcs[i][j]!= INFINITY)
			{
				setcolor(12);
				sprintf(str,"%d",G.arcs[i][j]);
				num(i,x1,y1,G);
				num(j,x2,y2,G);
				settextstyle(0,0,1);
				outtextxy((x1+x2)/2,(y1+y2)/2,str);
			}
		}
	}
}






 void main()
{
	MGraph G;
	int op;
	char xian1[N],xian2[N],str1[N],str2[N];
	G=Creat(xian1,xian2);
	int gd=DETECT,gm;
	initgraph(&gd,&gm,"D:\\TC\\BGI");
	setbkcolor(11);
	setcolor(1);
	cleardevice();
	MiniSpanTree_PRIM(G,G.vexs[0],str1,str2);
	printf("----  1.yuantu  ----\n");
	printf("----  2.MST     ----\n");
	printf("----  3.exit    ----\n");
	do
	{
		printf("input:");
		scanf("%d",&op);
		switch(op)
		{
		case 1:
			{
				 draw(xian1,xian2,G.arcnum,G,2,1,0);
				 output(G);
				 break;
			}
		case 2:draw(str1,str2,G.vexnum-1,G,1,3,1);break;
		case 3:break;
		default:printf("error!\n");
		}
	}while(op!=3);
}