#include<string> 
#include "LinkQueue.h"
#include "Mgraph.h"
#include <iostream>
using namespace std;

const MAX_ARCNUM=50;

// 最小生成树
//算法6.18 Prim算法
struct CEdge												// 候选边存储
{
	int adjvex;												// U中集合点
	int lowcost;											// 最小边的权值
};

int minEdge(CEdge closeEdge[],int n)
{
	int i, k=0;
	int min = INF; 
	for ( i=0; i<n; i++)									//求出与U权值最小的点 权值为0的代表在集合U
		{
			if (closeEdge[i].lowcost != 0 && closeEdge[i].lowcost<min)
			{
				min = closeEdge[i].lowcost;
				k = i;
			}
		}
	return k;
}


template<class DT>
bool Prim_MST(MGraph<DT> G, DT v)							// 从顶点v开始计算的最小生成树
{
	CEdge closeEdge[MAX_VEXNUM];
	int i,j,k,mincost = 0; 
	k=LocateVex(G,v);
	if(k==-1)												// 顶点不存在
	{
		cout<<"顶点不存在！"<<endl;
		return false;
	}
	for (i = 0; i < G.vexnum; i++)							// 辅助数组初始化
		if(i!=k)
		{
			closeEdge[i].adjvex = k;						// u中的点
			closeEdge[i].lowcost = G.arcs[k][i];	
	}
	closeEdge[k].lowcost=0;									// 初始 U={v}
	cout << "\n Prim最小生成树的边:"<< endl;
	for (i = 1; i < G.vexnum; i++)							// 选择其余G.vexnum-1个顶点
	{
		k=minEdge(closeEdge,G.vexnum);						// 输出选择的权值最小的边
		cout << "(" <<G.vexs[closeEdge[k].adjvex]<< "," << G.vexs[k] 
			<<"): "<<closeEdge[k].lowcost<<endl;
		mincost+=closeEdge[k].lowcost;
		closeEdge[k].lowcost=0;
		for (j = 0; j<G.vexnum; j++)							// 更新最小边
		{   
			if (closeEdge[j].lowcost != 0 && G.arcs[k][j]<closeEdge[j].lowcost)
			{   
				closeEdge[j].adjvex = k;
				closeEdge[j].lowcost= G.arcs[k][j];
			}
		}
 	}
	cout << "\n Prim最小生成树权值之和:" << mincost << endl;
	return true;
}

// Kruskal算法
struct Edge{													// 存储边的信息
	int u,v; 
	int cost;
};

//Edge edge[MAX_ARCNUM];
												
void Sort(Edge edge[],int n)									// 冒泡排序
{
	int i,j;
	//int k;
	Edge temp;
	bool exchange;
	for(i=0,exchange=true;i<n-1 && exchange; i++)				// 一趟排序工作如下： 
	{													
		exchange=false;											// 1.设置交换标志初值为无交换
		for(j=0;j<n-i-1;j++)									// 2.从表首开始两两比较
		{
			if (edge[j].cost>edge[j+1].cost)					// 2.1相邻元素逆序，互换位置
			{
				temp=edge[j];edge[j]=edge[j+1];edge[j+1]=temp;	// R[j]<-->R[j+1]
				exchange=true;									// 2.2 交换标志改为true
			}
		}
	}
}

int parent[MAX_VEXNUM]; 
void Connect(int &x,int &y)										// 连通分量标识
{
	if(x<y)
		y=x;
	else
		x=y;
} 

//算法6.19 克鲁斯卡尔（Kruskal）算法
template <class DT>
bool Kruskal_MST(MGraph<DT> G)										// 返回生成代价
{
   int mincost=0,Num_Edge=0;
   char u,v;
   int i,j,k=0;
   Edge edge[MAX_ARCNUM];
   for(i=0;i<G.vexnum;i++)											// 从邻接矩阵获取边信息
	   for(j=0;j<G.vexnum;j++)
	   {
		   if(i<j && G.arcs[i][j]!=INF)
		   {
			   edge[k].u=i;											// 存储边的信息
		       edge[k].v=j;
		       edge[k].cost=G.arcs[i][j];
			   k++;
		   }
	   }
	Sort(edge,G.arcnum);											// 边排序
	for(i=0;i<G.vexnum;i++)											// 连通分量初始化
	{
		parent[i]=i;
	}
	cout << "\n Kruskal 最小生成树的边:"<< endl;
	for(i=0;i<G.arcnum;i++)											// 从小到考察选取n-1条边
	{
		j=edge[i].u;
		k=edge[i].v;
		int vx1=parent[j];											// 获取边起点、终点所在的连通分量标志
		int vx2=parent[k];
		if(vx1!=vx2)												// 如果不属于同一个连通分量, 生成边
		{
			GetVex(G,j,u);
			GetVex(G,k,v);
			cout<<"("<<u<<","<<v<<"):"<<G.arcs[j][k]<<endl;
			Connect(parent[j],parent[k]);							// 合并连通分量
			mincost+=edge[i].cost;
			Num_Edge++;												// 已找到的边数+1
			if(Num_Edge==G.vexnum-1)
				break; 
		}
	
	}
	if(Num_Edge!=G.vexnum-1)										// 判断最小生成树的查找情况
	{
		cout<<"非连通图，无最小生成树！"<<endl;
		return false;
	}
	else
	{
		cout<<"\nKruskal最小生树权值为："<<mincost<<endl;
		return true;
	}
}


void DispMenu()
{
	cout<<"\n 请选择你要的操作"<<endl;
	cout<<" 1. 建立无向网"<<endl;
	cout<<" 2. Prinmt算法"<<endl;
	cout<<" 3. Kruskal算法"<<endl;
	cout<<" 4. 显示网"<<endl;
	cout<<" 0. 退出"<<endl;
}

bool visited[MAX_VEXNUM]={false};

void main()
{
	char v;
	//int k,weight;
	MGraph<char> G;
	int choice;
	do
	{
		DispMenu();
		cin>>choice;
		switch(choice)
		{
			case 1:														// 创建无向网
					CreateUDN(G);
					cout<<endl;
					cout<<"创建的网为："<<endl;
					DispG(G);
					break;
			case 2:														// Prinmt算法
					cout<<"请输入起始计算顶点:  ";
					cin>>v;
					Prim_MST(G,v);
					break;
			case 3:														// Kruskal算法
					Kruskal_MST(G);
					cout<<endl;
					break;
			case 4:														// 显示网
					DispG(G);
					cout<<endl;
					break;
			case 0:
					cout<<"结束运行，Bye-Bye!"<<endl;
					break;
			default:
					cout<<"选择不合理，请重选!"<<endl;
			}//case
		}while(choice!=0);
}//main