#include "stdio.h"
#include "stdlib.h"

#define MAX_VERTEX_NUM 30			//圖的最大節點數


typedef char VERTEXTYPE;	//定義圖的節點類型

typedef struct ArcCell	// 弧的定義
{ 
	int adj;			// 對無權圖，用1或0表示相鄰否；對帶權圖，則為權值類型。
    //InfoType *info;		// 該弧相關信息的指針
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct // 圖的定義
{  
	VERTEXTYPE  vexs[MAX_VERTEX_NUM];       // 頂點信息
    AdjMatrix  arcs;		// 弧的信息                     
    int  vexnum, arcnum;	// 頂點數，弧數             
} MGraph;

int LocateVex(MGraph G, VERTEXTYPE v)
{
	int locate=0;
	while( G.vexs[locate]!=v && locate<G.vexnum )locate++;
	if(locate==G.vexnum)
	{
		printf("該節點不存在！\n");
		return(locate);
	}
	else return(locate);
}

void CreateUDN(MGraph &G)      //建無向網的鄰接矩陣表示
{
	int i,j,k,w;
	VERTEXTYPE v1,v2;
	printf("請輸入圖中節點和弧的個數，中間以逗號間隔：\n");
	scanf("%d,%d",&G.vexnum,&G.arcnum);
	getchar();	//用來接收回車符
	printf("請輸入節點向量，中間不需要間隔：\n");
	for( i=0; i<G.vexnum; i++ ) G.vexs[i]=getchar();	//構造頂點向量
	getchar();	//用來接收回車符
	//for( i=0; i<G.vexnum; i++ ) printf("%c",G.vexs[i]);
	for( i=0; i<G.vexnum; i++ )
       for( j=0; j<G.vexnum; j++ ) G.arcs[i][j].adj=1000;	//初始化鄰接矩陣,1000表示最大權值
	printf("請輸入每條邊依附的頂點和權值，中間以逗號間隔：\n");
	for( k=0; k<G.arcnum; k++ )
    { 
		scanf("%c,%c,%d",&v1,&v2,&w);		//輸入一條邊依附的頂點和邊的權值
		getchar();	//用來接收回車符
		i=LocateVex(G,v1);
		j=LocateVex(G,v2);
        G.arcs[i][j].adj=w;			//修改鄰接矩陣
		G.arcs[j][i].adj=w;			//修改鄰接矩陣
	}
}//   時間復雜度為O(n2)

typedef struct
{
	VERTEXTYPE adjvex;
	int lowcost;
}Closedge[MAX_VERTEX_NUM];

Closedge closedge;

int minimum(Closedge closedge,MGraph G)
{
	int i=0, m=1000;		//先規定1000為最大權值
	for( int j=0; j<G.vexnum; j++ )
		if(closedge[j].lowcost>0)
			if(closedge[j].lowcost<m)
			{
				m=closedge[j].lowcost;
				i=j;
			}
	return(i);
}

void MiniSpanTree_P(MGraph G, VERTEXTYPE u)		//用普里姆算法從頂點u出發構造網G的最小生成樹
{ 
	int k = LocateVex( G, u ); 
	for( int j=0; j<G.vexnum; j++ )	//輔助數組初始化
		if(j!=k) 
		{
			closedge[j].adjvex=u;
			closedge[j].lowcost=G.arcs[k][j].adj;
		}  
	closedge[k].lowcost = 0;      //初始，U＝{u}
	for (int i=1; i<G.vexnum; i++) 
	{
		k = minimum(closedge,G);	//求出加入生成樹的下一個頂點(k)                  
		printf("%c%c\n",closedge[k].adjvex, G.vexs[k]);	// 輸出生成樹上一條邊 
		closedge[k].lowcost = 0;	// 第k頂點并入U集
		for(j=0; j<G.vexnum; ++j)	//修改其它頂點的最小邊        
		if( G.arcs[k][j].adj < closedge[j].lowcost)
		{
			closedge[j].adjvex=G.vexs[k];
			closedge[j].lowcost=G.arcs[k][j].adj;
		}
	}//for
}