#include <stdio.h>
#define MAX  1000
#define MAXNode 20

typedef struct
{
 int vexnum,arcnum;
 int arcs[MAXNode][MAXNode];
}MGraph;//用鄰接矩陣存儲


void CreateMGraph(MGraph *p)
{
  int i,j,n,m;
  int v1,v2,w;
  printf("請輸入頂點個數:"); 
  scanf("%d",&n); 
  p->vexnum=n;
  printf("請輸入邊數:");
  scanf("%d",&m);
  p->arcnum=m;
  for(i=0;i<n;++i)
   for(j=0;j<n;++j)
    if(i==j)
     p->arcs[i][j]=0;
    else
     p->arcs[i][j]=MAX;//鄰接矩陣初始化

 for(i=1;i<=m;i++)
 {
   printf("請輸入第%d條邊的頂點序號v（0<=v<=%d）及該邊權值：",i,n);
   scanf("%d %d %d",&v1,&v2,&w);
   if(v1>=0&&v1<n&&v2>=0&&v2<n)
   {
	 p->arcs[v1][v2]=w;
  	 p->arcs[v2][v1]=w;
   }//if
 }//for
}


int prim(MGraph G,int v)
{//用prim算法從序號為v的頂點出發構造最小生成樹
	//并返回權值和
	int i,j,k,min,c=0;
	int lowcost[MAXNode],closest[MAXNode];
	for(i=0;i<G.vexnum;++i)
	{//對每一個結點
		closest[i]=v;//初值最近點
		lowcost[i]=G.arcs[v][i];
	}
 
 for(i=0;i<G.vexnum-1;i++)
 {
	min=MAX;
	for(j=0;j<G.vexnum;++j)
	  //在余下的頂點中找出最近的那個，并用k記下其序號
	if(lowcost[j]!=0&&lowcost[j]<min)
	{
		min=lowcost[j];
		k=j;
	}

	printf("v%d-v%d\t%d\n",closest[k],k,min);
	c+=min;

	lowcost[k]=0;//將此點歸并
	for(j=0;j<G.vexnum;++j)
	 if(G.arcs[k][j]!=0&&G.arcs[k][j]<lowcost[j])
	 {
		lowcost[j]=G.arcs[k][j];
		closest[j]=k;
	 }

 }
 return c;
}


/*int Kruskal(Graph G)
{//用Kruskal算法從序號為0的頂點出發構造最小生成樹
	//并返回權值和
int i,j,min,c=0,k;
for(i=0;i<G.vexnum;i++)
{//對每一個結點
	min=MAX;
	for(j=0;j<G.vexnum;++j)
	{	if(i!=j&&G.arcs[i][j]<min)
			min=G.arcs[i][j];
			k=j;
	}
			G.arcs[k][i]=MAX;
			printf("v%d-v%d %d\n",i,k,min);
			c+=min;
	}
	return c;

}*/


void Prim()
{
 int cost;
 MGraph G;
 CreateMGraph(&G);
 printf("prim得的最小生成樹為:\n");
 printf("邊\t 權值\t\n");
 cost=prim(G,0);
 printf("Cost :   %d\n",cost);
}