www.pudn.com > ret.rar > ret.cpp

#include 
#include 
#include 
#include 
#include 
 
 
#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  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