#include <stdio.h>
#include <stdlib.h>
#define VertexMax 100 //最大頂點數(shù)為100
#define MaxInt 32767 //表示最大整數(shù)，表示 ∞ 

typedef char VertexType; //每個頂點數(shù)據(jù)類型為字符型 

//鄰接矩陣結(jié)構(gòu)體 
typedef struct{
	//存放頂點元素的一維數(shù)組 
	VertexType Vertex[VertexMax];
	//鄰接矩陣二維數(shù)組 
	int AdjMatrix[VertexMax][VertexMax];
	//圖的頂點數(shù)和邊數(shù) 
	int vexnum,arcnum;
}MGraph;

//輔助數(shù)組結(jié)構(gòu)體(候選最短邊) 
typedef struct{
	//候選最短邊的鄰接點 
	VertexType adjvex;
	//候選最短邊的權(quán)值 
	int lowcost;
	/*
	 ? lowcost = 0：表示 這個頂點已經(jīng)放入 U集合中（即 已經(jīng)生成的最小部分生成樹） 
	 ? 將 lowcost 置為 0，代表加入 U集合
	 ? lowcost 中記錄的是 V0 到其它頂點的代價 
	
	 ?從 上一次求得的最短鄰接邊 出發(fā) 到 V集合中的頂點，將 其代價 與 lowcost數(shù)組中的值進行比較 
	*/
}ShortEdge; // ShortEdge數(shù)組下標(biāo) 表示 頂點序號 

//查找 頂點v 在一維數(shù)組 Vertex[] 中的下標(biāo)，并返回下標(biāo)
int LocateVertex(MGraph *G, VertexType v){
	int i;
	for(i = 0; i < G->vexnum; i++){
		if(v == G->Vertex[i]){
			return i; 
		} 
	} 
	return -1;
}

//構(gòu)建無向網(wǎng)（Undirected Network）
void CreateUDN(MGraph *G){
	int i, j;
	// 1.輸入頂點數(shù)和邊數(shù)
	printf("請輸入頂點個數(shù)和邊數(shù)：\n");
	printf("頂點數(shù) n = "); 
	scanf("%d", &G->vexnum);
	printf("邊 ?數(shù) e = "); 
	scanf("%d", &G->arcnum);
	printf("\n\n"); 
	
	// 2.輸入頂點元素 
	printf("輸入頂點元素(無需空格隔開)：");
	scanf("%s", &G->Vertex);
	
	printf("\n\n");
	
	// 3.鄰接矩陣初始化
	for(i = 0; i < G->vexnum; i++){
		for(j = 0; j < G->vexnum; j++){
			if(i == j){
				G->AdjMatrix[i][j] = 0;
			}
			else{
				G->AdjMatrix[i][j] = MaxInt;
			}
	 ? ?	
		}
	} 
	 
	// 4.構(gòu)建鄰接矩陣
	int n, m;
	VertexType v1, v2;
	// 頂點 v1、v2之間的權(quán)值 
	int w;
	 
	printf("請輸入邊的信息和權(quán)值(例：A B 15)：\n");
	// for循環(huán)：邊數(shù) 
	for(i = 0; i < G->arcnum; i++){
		printf("請輸入第 %d 條邊信息及權(quán)值：",i+1);
		// 注：%c 前面需要添加空格符號 
	 	scanf(" %c %c %d", &v1,&v2,&w);
	 	
	 	//獲取 v1、v2 所對應(yīng)的在Vertex數(shù)組中的坐標(biāo) 
	 	n = LocateVertex(G, v1); 
	 	m = LocateVertex(G, v2); 
	 	// 輸入邊的信息非法，重新輸入 
	 	while(n == -1 || m == -1){
	 		printf("沒有該邊信息!\n");
	 		printf("請重新輸入第 %d 條邊信息及權(quán)值：", i+1);
	 		// 注：%c 前面需要添加空格符號 
	 		scanf(" %c %c %d", &v1, &v2, &w);
	 		n=LocateVertex(G, v1); 
	 		m=LocateVertex(G, v2); 
		} 
	 	// 將鄰接矩陣相應(yīng)位置賦上權(quán)值 
		G->AdjMatrix[n][m]=w;
	 ? 	G->AdjMatrix[m][n]=w;
 ? ?} 
}

// 輸出無向圖 
void print(MGraph G){
	int i,j;
	printf("\n-------------------------------");
	printf("\n 鄰接矩陣：\n\n"); 	
	
	printf("\t ");
	for(i = 0; i < G.vexnum; i++){
		printf("\t%c", G.Vertex[i]);
	}
	
	printf("\n");
		 
	for(i = 0; i < G.vexnum; i++){
 ? 		printf("\t%c", G.Vertex[i]);
 ? 	 ?	for(j = 0; j < G.vexnum; j++){
 ? ?		if(G.AdjMatrix[i][j] == MaxInt){
 ? ?			printf("\t∞");
			}
			else{
				printf("\t%d", G.AdjMatrix[i][j]);
			}
 ? ?	}
 ? ? ?	printf("\n");
 ? ?}	 
}
 
//找最短路徑的頂點 （在 lowcost中 尋找 最小代價的頂點） 
// 注意：需要將 lowcost值已經(jīng)為 0 的頂點排除掉 
int minimal(MGraph *G, ShortEdge *shortedge){
	int i, j;
	int min, locate;
	
	min = MaxInt;
	for(i = 0; i < G->vexnum; i++){
		// 代價最小 并且 不屬于U集合 
		if(min > shortedge[i].lowcost && shortedge[i].lowcost != 0){
			min = shortedge[i].lowcost;
			// lowcost數(shù)組下標(biāo) 表示 頂點序號 
			locate = i;
		}
	}
	// 返回 目前能到達的最小頂點（數(shù)組下標(biāo) 表示 頂點序號 ） 
	return locate;
}

/*
	輸出 最小生成樹 路徑 
	shortedge[5].adjvex = 0, shortedge[5].lowcost = 19
	表示 從 頂點0 出發(fā) 到達最短頂點5，代價為19 
*/
void outputMST(MGraph *G, VertexType k, ShortEdge shortedge[]){
	//輸出找到的最短路徑頂，及路徑權(quán)值 
	printf("%c -> %c, weight = %d\n", shortedge[k].adjvex, G->Vertex[k], shortedge[k].lowcost);
}
 
// 最小生成樹-普利姆算法 
void MiniSpanTree_Prim(MGraph *G, VertexType start){ 
	int i, j, k;
	ShortEdge shortedge[VertexMax];
	
	// 1.處理起始點start 
	k = LocateVertex(G, start);
	
	// 初始化輔助數(shù)組 shortedge（即 從開始頂點 到 其余頂點的代價） 
	for(i = 0; i < G->vexnum; i++){
		// 開始頂點start ?到 ? 頂點i 
		shortedge[i].adjvex = start;
		shortedge[i].lowcost = G->AdjMatrix[k][i];
	}
	// 將 起點start 放入集合U（已經(jīng)生成的 部分最小生成樹） 
	shortedge[k].lowcost = 0; //lowcost為0表示該頂點屬于U集合 
	
	// 2.處理后續(xù)結(jié)點 
	//對集合U，去找最短路徑的頂點 
	// 總共 vexnum 個頂點，開始頂點 已經(jīng)處理了，因此只需要處理 vexnum - 1 個頂點 
	for(i = 0; i < G->vexnum-1; i++){
		//找 到達最短路徑 的頂點 
		k = minimal(G, shortedge);
		//輸出找到的最短路徑頂，及路徑權(quán)值 
		outputMST(G, k, shortedge); 
	 ? ?
	 ? ?//將找到的最短路徑頂點加入集合U中，U集合擴展 
	 ? ?shortedge[k].lowcost = 0; 
	 ? ?
	 ? ?/* 
	 ? ? ? ?U集合中加入了新節(jié)點，通過 新加入節(jié)點 到達其他節(jié)點，
		 ? 可能出現(xiàn)新的最短路徑，故更新shortedge數(shù)組 ?
		*/
	 ? ?for(j = 0; j < G->vexnum; j++){ // 遍歷 K頂點 到其他頂點 
			//有更短路徑出現(xiàn)時，更新shortedge數(shù)組	 
	 ? ?	// 從 上一次求得的頂點 出發(fā) 到 V集合中的頂點，將 其代價 與 lowcost數(shù)組中的值進行比較 
	 ? ?	// G->AdjMatrix[k][j]：從 上一次求得的頂點 出發(fā) 到 V集合中的頂點 
	 ? ?	if(G->AdjMatrix[k][j] < shortedge[j].lowcost){
	 ? ?		// 到達頂點 j 的最短距離，從 K 到 j 
	 ? ?		shortedge[j].lowcost = G->AdjMatrix[k][j];
				// 經(jīng)由 K 頂點，到達 j 頂點
	 ? ?		shortedge[j].adjvex = G->Vertex[k];
			}
		}
	} 
}

int main(){
	
	VertexType start;
	MGraph G;
	
	CreateUDN(&G);
	print(G); 
	
	while(true){
		printf("請輸入起始點：");
		// 注：%c 前面需要添加空格符號 
		scanf(" %c", &start);
		MiniSpanTree_Prim(&G, start);
		int flag;
		printf("\n是否繼續(xù)進行測試？（1：是，0：否）\n");
		scanf("%d", &flag);
		if(flag == 0){
			break;
		}
	} 
	
	return 0;
}