#include<stdio.h>
#ifdef _WIN32
	#include<Windows.h>
#endif

#define MAX_VERTICES 8
#define MAX_EDGES 12

#define TRUE 1
#define FALSE 0
#define INF 1000L

typedef struct _dist
{
	int dist[MAX_VERTICES];
	char edge[MAX_VERTICES][2];
}dist;

int weight[MAX_VERTICES][MAX_VERTICES];

int selected[MAX_VERTICES];
dist dists;

int get_min_vertex(int n)
{
	int v,i;

	for(i=0;i<n;i++)
	{
		if(!selected[i])
		{
			v = i;
			break;
		}
	}

	for(i=0;i<n;i++)
	{
		if(!selected[i] &&(dists.dist[i] < dists.dist[v]))
		{
			v = i;
		}
	}

	return (v);
}

void prim(int s,int n)
{
	int i,u,v;

	for(u=0;u<n;u++)
	{
		dists.dist[u]=INF;
		selected[u] = FALSE;
	}
	dists.dist[s] = 0;

	for(i=0;i<n;i++)
	{
		u=get_min_vertex(n);
		selected[u] = TRUE;
		if(dists.dist[u] == INF)
		{
			return;
		}
		if(u != s)
		{
			printf("(%c, %c) ",dists.edge[u][0],dists.edge[u][1]);
		}

		for(v=0;v<n;v++)
		{
			if(weight[u][v]!=INF)
			{
				if(!selected[v] && weight[u][v]<dists.dist[v])
				{
					dists.dist[v] = weight[u][v];
					dists.edge[v][0] = 65+u;
					dists.edge[v][1] = 65+v;
				}
			}
		}
	}
}

int main()
{
	int i,j;
	int u,v,temp;
	char u_temp,v_temp;

	for(i=0;i<MAX_VERTICES;i++)
	{
		for(j=0;j<MAX_VERTICES;j++)
		{
			if(i==j)
			{
				weight[i][j] = 0;
			}else
			{
				weight[i][j] = INF;
			}
		}
	}
	printf("정점의 개수와 간선의 개수를 그래프에 맞게 변경하셨나요\n");
	printf("정점_1 정점_2 가중치를 다음 형태대로 입력하세요\n");
	printf("예제) a b 10\n\n");
	for(i=0;i<MAX_EDGES;i++)
	{
		scanf("%c %c %d",&u_temp,&v_temp,&temp);
		while( getchar() != '\n' );
		u = (int)u_temp - 97;
		v = (int)v_temp - 97;
		weight[u][v] = temp;
		weight[v][u] = temp;
	}
	
	prim(0,MAX_VERTICES);

	system("PAUSE");
	return 0;
}