ret.cpp

实现最小生成树问题,在N个城市之间寻找最短路径

#include<stdio.h>
#include<iostream.h>
#include<malloc.h>
#include<conio.h>
#include<stdlib.h>


#define MAX_V 100
#define MAX 10
#define TURE 1
#define FALSE 0


//城市的名称
typedef struct{
	int vertex1;
	int vertex2;
	int weight;  //城市的距离
    int edge_deleted;
}Edge;         //两城市间的相关信息
			 
char vex[MAX][MAX];

Edge E[MAX_V];

int total_vertex;  //顶点数  城市的数量

int total_edge;   //边数  两城市的连线数

int adjmatrix[MAX_V][MAX_V];   //以矩阵的形式来表示城市的关系

void kruskal();  //Kruskal算法

void addEdge(Edge);  //用来存入边

void build_adjmatrix();  //用城市的信息存入文件

Edge mincostEdge();  //用来求最小的边

void showEdge();   //用来初始时的显示

void prim(int u);   //prim算法

int minimum();   //Prim算法中求最小边的点

void print()      // 界面输出
{
	cout<<"\t\t#######################################\n";
	cout<<"\t  ##\t\t\t\t\t\t  ##\n";
	cout<<"\t  ##\t\t  数据结构程序设计\t\t  ##\n";
	cout<<"\t  ##\t\t\t\t\t\t  ##\n";
	cout<<"\t  ##\t\t\t\t\t\t  ##\n";
	cout<<"\t  ##\t  本程序由汤徐盛 何学瑾 蔡慧锋完成\t  ##\n";
	cout<<"\t  ##\t\t\t\t\t\t  ##\n";
	cout<<"\t  ##\t\t\t\t\t\t  ##\n";
	cout<<"\t  ##\t\t\t\t\t\t  ##\n";
	cout<<"\t\t#######################################\n";
}

struct{
	int adjvex;
	int lowcost;
}closedge[MAX_V];  //用定义顶点与距离

void main()    //主函数
{
	printf("\t\t\t数据结构程序设计\n");
	printf("\n\n");
	cout<<"\t\t#######################################\n";
	cout<<"\t  ##\t\t\t\t\t\t  ##\n";
	cout<<"\t  ##\t\t  数据结构程序设计\t\t  ##\n";
	cout<<"\t  ##\t\t\t\t\t\t  ##\n";
	cout<<"\t  ##\t\t\t\t\t\t  ##\n";
	cout<<"\t  ##\t  本程序由汤徐盛 何学瑾 蔡慧峰完成\t  ##\n";
	cout<<"\t  ##\t\t\t\t\t\t  ##\n";
	cout<<"\t  ##\t\t\t\t\t\t  ##\n";
	cout<<"\t  ##\t\t\t\t\t\t  ##\n";
	cout<<"\t\t####################################\n";
	print();
	getch();
	system("cls");
	printf("\n\n");
	printf("\t\t利用最小生成树解决最经济的网络连通\n");	
	printf("\n\n\n\n");
	getch();
	Edge e;
	int i, j, weight;
	build_adjmatrix();
    for(i=1;i<=total_vertex;i++)                 //将文件中的值复给边
		for(j=i+1;j<=total_vertex;j++)
		{
			weight=adjmatrix[i][j];    
			if(weight!=0)                      //将不为零的边存入addEdge中
			{
				e.vertex1=i;
				e.vertex2=j;
				e.weight=weight;
				e.edge_deleted=FALSE;
				addEdge(e);
			}
		}
	
	showEdge();	        
	printf("\n");
	getch();
	printf("由kruskal算法得:\n");
	printf("\t\t**********\n");
	kruskal();	
	getch();
	printf("\n\n");
	printf("prim算法得:\n");
	printf("\t\t**********\n");
	prim(1); //以顶点V1开始进行prim算法
	
}//main
 
void build_adjmatrix()
{ 
	FILE *fptr;
	FILE *fp;
	int vi,vj,i;
	
    fptr=fopen("kruskal.txt","r");     //以读的形式打开文件kruskal
	fp=fopen("name.txt","r");       //以读的形式打开文件kruskal1
 
	if(fptr==NULL)                  //判断文件kruskal是否为空
	{
		perror("name.txt");
		exit(0);
	}
	if(fptr==NULL)           //判断文件kruskal1是否为空
	{
		perror("kruskal.txt");
		exit(0);
	}
   
	fscanf(fptr,"%d",&total_vertex);    //将kruskal文件中的城市的各数存入顶点数中(total_vertex)
	printf("以下是所需网络连接的城市:\n");
	for(i=0;i<total_vertex;i++)     //将文件kruskal1中的地名存入vex[]数组中
	{
		fscanf(fp,"%s",vex[i]);
		cout<<endl;
		printf("\t\tV%d顶点表示的地名为:%s\n",(i+1),vex[i]);
			
	}
	getch();
	for(vi=1;vi<=total_vertex;vi++)    //读取文件kruskal
		for(vj=1;vj<=total_vertex;vj++)
			fscanf(fptr,"%d",&adjmatrix[vi][vj]);
	fclose(fptr);
	fclose(fp);
}//build_adjmatrix


void addEdge(Edge e)
{
	E[++total_edge]=e;
}
//addEdge

void showEdge()
{
	int i=1;
	cout<<endl;
	printf("地名的个数:    total_vertex=%d \n",total_vertex);   
	printf("网络连线的个数:    total_edge=%d \n",total_edge);   //边的各数
	cout<<endl;
	printf("以下是各个边的表示:\n");
    cout<<endl;
	while(i<=total_edge)   //小于边的各数
	{
		printf("\t\tV%d  <------->  V%d    weight=%d\n",E[i].vertex1,E[i].vertex2,E[i].weight);
		i++;
	}
}


Edge mincostEdge()
{
	int i,min;
	long minweight=100000;  
	for(i=0;i<=total_edge;i++)
	{
		if(!E[i].edge_deleted && E[i].weight<minweight)  //从中选出最不的边而且没有用过的
		{
			minweight=E[i].weight;
			min=i;
		}
	}
	E[min].edge_deleted=TURE;   //表示E[min]以被用过
	return E[min];

}//mincostEdge

void kruskal()
{
	Edge e;

	int i,j;
	int loop=1;
	int k;
	int  s[MAX_V][MAX_V];  //用于表示集合
	for (i=1; i<=total_vertex;i++){   //将顶点分别置于不同的集合中
		for(j=1;j<=total_vertex;j++)
		{
			if(i==j) s[i][j]=TURE;
			else s[i][j]=FALSE;
		}
	}
	int f=1,d=0,m1,m2;
	
	while(f<total_vertex){	
		e=mincostEdge();  //取出最小边
		
		for(i=1;i<=total_vertex;i++)   //判断边的头顶点属于哪一个集合
		{
			if(s[i][e.vertex1]==1)   m1=i;
		}
	         
		for(i=1;i<=total_vertex;i++)   //判断边的尾顶点属于哪一个集合
		{
			if(s[i][e.vertex2]==1)   m2=i;
		}
		
		if(m1!=m2)   //判断头尾顶点是否属于同一个集合
		{
			printf("\t\t最小生成树的第%d条边为: ",loop++);
			printf("V%d----V%d   weight=%d\n",e.vertex1,e.vertex2,e.weight);
			for(k=1;k<=total_vertex;k++)   //合并头尾所属的两个集合
			{
				s[m1][k]=s[m1][k]||s[m2][k];
				s[m2][k]=FALSE;
			}
			f++;
		}	
	}
}//kruskal


int minimum()   //Prim算法中求最小边的点
{
	int i;
	int j;
	int tem=1000000;
	for(i=1;i<=total_vertex;i++)
	{
		if(closedge[i].lowcost!=0)   //属于集合closedge[i].lowcost中最小的边的顶点
		{
			if(closedge[i].lowcost<tem){
				tem=closedge[i].lowcost;
				j=i;
			}		
		}
	}
    
	return j;
}


void prim(int u)   //prim算法
{
	
	int j;
	int i;
	int k;
	for(j=1; j<=total_vertex;j++)
	{
		if(j!=u){    //将顶点u定义为一个集合
			closedge[j].adjvex=u;
			closedge[j].lowcost =adjmatrix[u][j];
		}
	}
	printf("\t\t先由V%d顶点开始\n",u);
	closedge[u].lowcost=0;
	for(i=2;i<=total_vertex;i++)
	{	k=minimum();         //求小边的顶点
		cout<<"\t\t接着"<<"V"<<closedge[k].adjvex<<"顶点与"<<"V"<<k<<"相连     ";
		cout<<"生成边的长度为"<<closedge[k].lowcost<<"\n";
	    closedge[k].lowcost=0;
		for(j=1;j<=total_vertex;j++)
		{
			if(adjmatrix[k][j]<closedge[j].lowcost){   //将顶点k加入closedge[j].lowcost中
				closedge[j].adjvex=k;
				closedge[j].lowcost=adjmatrix[k][j];
			}
		}
	}
	cout<<endl;
	getch();
}