#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();
}