/* =============== Program Description =============== */
/* 程序名稱： prims.c                                  */
/* 程序目的： 設計一個利用Prims算法找出生成樹的程序  */
/* Written By Kuo-Yu Huang. (WANT Studio.)             */
/* =================================================== */
#include <stdlib.h>
#define Max 10
#define VertexNum 5

struct	List				/* 節(jié)點結構聲明 */
{
	int		Marked;		/* 搜索標記 */
	int		Vertex1;	/* 頂點聲明 */
	int		Vertex2;	/* 頂點聲明 */
	int		Weight;		/* 加權值 */
	struct	List	*Next;
};
typedef	struct	List	Node;
typedef	Node	*Edge;			/* 定義鄰接邊的節(jié)點 */

int Edges[10][3] =	/* 輸入數據 */
	{ 	{1,2,7}, {1,3,6}, {1,4,5}, {1,5,12}, {2,3,14},
		{2,4,8}, {2,5,8}, {3,4,3}, {3,5,9}, {4,5,2} };

int Visited[VertexNum+1];	/* 搜索記錄 */

/* --------------------------------------------------- */
/* Prims算法                                       */
/* --------------------------------------------------- */
void Prims(Edge Head,int Index)
{
	Edge	Pointer;	/* 節(jié)點聲明 */
	Edge	MinEdge;
	int		EdgeNum = 0;	/* 已連結邊的數目 */
	int		Weight = 0;	/* 累計加權值 */
	int		i;

	Visited[Index] = 1;	/* 設定已搜索過 */

			/* 當邊的數目為頂點的數目減1時，結束循環(huán) */
	while ( EdgeNum != ( VertexNum - 1 )  )
	{
		MinEdge->Weight = 999;		/* 將最小邊的加權值設到最大 */
		for ( i=1;i<=VertexNum;i++ )	/* 判斷未建立的鄰接頂點 */
		{
			Pointer = Head;
			if ( Visited[i] == 1 )	/* 已存在生成樹集合的頂點 */
			{
				while ( Pointer->Marked == 1 )	/* 往下一個未建立的鄰接邊 */
					Pointer = Pointer->Next;
				if ( MinEdge->Weight > Pointer->Weight )
					MinEdge = Pointer;	/* 找出加權值最小的鄰接邊 */
				while (	Pointer != NULL )
				{
				/* 如果兩頂點皆存在生成樹集合中，表示是已搜索過的邊 */
					if ( Visited[Pointer->Vertex1] == 1
					&& Visited[Pointer->Vertex2] == 1 )
						Pointer->Marked = 1;
				/* 找出加權值最小的鄰接邊 */
					if ( MinEdge->Weight > Pointer->Weight
						&& Pointer->Marked == 0
						&& ( Pointer->Vertex1 == i
							|| Pointer->Vertex2 == i ) )
						MinEdge = Pointer;
					Pointer = Pointer->Next;
				}
			}
		}
		Visited[MinEdge->Vertex1] = 1;	/* 將頂點1設為存在生成樹集合中 */
		Visited[MinEdge->Vertex2] = 1;	/* 將頂點2設為存在生成樹集合中 */
		EdgeNum++;			/* 生成樹的邊數加1 */
		Weight += MinEdge->Weight;	/* 累計加權值 */
		printf("[%d,%d]",MinEdge->Vertex1,MinEdge->Vertex2);
		printf("(%d)",MinEdge->Weight);
	}
	printf("\nTotal weight = %d\n",Weight);	/* 輸出加權值總和 */
}

/* --------------------------------------------------- */
/* 釋放鏈表                                        */
/* --------------------------------------------------- */
void Free_Edge(Edge Head)
{
	Edge	Pointer;		/* 節(jié)點聲明 */

	while (	Head != NULL )	/* 當節(jié)點為NULL結束循環(huán) */
	{
		Pointer = Head;
		Head = Head->Next;	/* 往下一個節(jié)點 */
		free(Pointer);
	}
}

/* --------------------------------------------------- */
/* 輸出鏈表數據                                    */
/* --------------------------------------------------- */
void Print_Edge(Edge Head)
{
	Edge	Pointer;		/* 節(jié)點聲明 */

	Pointer = Head;			/* Pointer指針設為首節(jié)點 */
	while (	Pointer != NULL )	/* 當節(jié)點為NULL結束循環(huán) */
	{
		printf("[%d,%d]",Pointer->Vertex1,Pointer->Vertex2);
		printf("(%d)",Pointer->Weight); /* 輸出加權值 */
		Pointer = Pointer->Next;	/* 往下一個節(jié)點 */
	}
	printf("\n");
}

/* --------------------------------------------------- */
/* 插入鄰接邊至鏈表中                              */
/* --------------------------------------------------- */
Edge Insert_Edge(Edge Head,Edge New)
{
	Edge	Pointer;		/* 節(jié)點聲明 */

	Pointer = Head;			/* Pointer指針設為首節(jié)點 */

	while ( Pointer->Next != NULL )	/* 插入在鏈表尾端 */
		Pointer = Pointer->Next;
	Pointer->Next = New;

	return Head;
}

/* --------------------------------------------------- */
/* 建立鏈表                                        */
/* --------------------------------------------------- */
Edge Create_Edge(Edge Head)
{
	Edge	New;			/* 節(jié)點聲明 */
	Edge	Pointer;		/* 節(jié)點聲明 */
	int	i;

	Head = (Edge) malloc(sizeof(Node));	/* 存儲空間配置 */

	if ( Head == NULL )
		printf("Memory allocate Failure!!\n");	/* 存儲空間配置失敗 */
	else
	{
		Head->Marked = 0;
		Head->Vertex1 = Edges[0][0];
		Head->Vertex2 = Edges[0][1];
		Head->Weight = Edges[0][2];	/* 定義節(jié)點加權值 */
		Head->Next = NULL;

		for ( i=1;i<10;i++ )
		{
			New = (Edge) malloc(sizeof(Node));

			if ( New != NULL )
			{
				New->Marked = 0;
				New->Vertex1 = Edges[i][0];
				New->Vertex2 = Edges[i][1];
				New->Weight = Edges[i][2];/* 定義節(jié)點加權值 */
				New->Next = NULL;

				Head = Insert_Edge(Head,New);/* 則插入新節(jié)點 */
			}
		}
	}
	return Head;
}
/* --------------------------------------------------- */
/* 主程序                                              */
/* --------------------------------------------------- */
void main ()
{
	Edge	Head;			/* 節(jié)點聲明 */
	int	i;

	for ( i=1;i<=VertexNum;i++ )	/* 清除搜索記錄 */
		Visited[i] = 0;

	Head = Create_Edge(Head);	/* 調用建立鏈表 */
	Print_Edge(Head);

	if ( Head != NULL )
	{
		printf("Prims Algorithm : \n");
		printf("Start from Vertex 1.\n");
		printf("Find Minimal Spanning Tree.\n");

		Prims(Head,1); 		/* 調用Prims算法 */
		free(Head);		/* 調用釋放鏈表 */
	}
}