#include "stdlib.h"        /* For _MAX_PATH definition */
#include "stdio.h"
#include "malloc.h"
#include "conio.h"
#include "ctype.h"
#include "iostream.h"

#define MAX  50
int n,c[100][100];
void prim()
{
  int i,j,k,min;
  int *lowcost;
  int *closest;
  int *s;
  
  lowcost=(int*)malloc(sizeof(int)*(n+1));
  closest=(int*)malloc(sizeof(int)*(n+1));
  s=(int*)malloc(sizeof(int)*(n+1));
  s[1]=1;
  
  for(i=2;i<=n;i++)
  {
    lowcost[i]=c[1][i];
    closest[i]=1;
    s[i]=0;
  }
  for(i=1;i<n;i++)
  {
    min=MAX;
    j=1;
    
	for(k=2;k<=n;k++)
       if((lowcost[k]<min)&&(!s[k]))
	   {
          min=lowcost[k];
          j=k;
	   }
     
	   cout<<"("<<j<<","<<closest[j]<<")"<<"      "<<"成本為：";
	   if(j>closest[j])
	   {
		   cout<<c[closest[j]][j];
	   }
	    if(j<closest[j])
		{
			cout<<c[j][closest[j]];
		}
		cout<<endl;
	
		s[j]=1 ;
    
	for(k=2;k<=n;k++)
      if((c[j][k]<lowcost[k])&&(!s[k]))
	  {
         lowcost[k]=c[j][k];
         closest[k]=j;
	  }
  }
}

void main()
{
   int i,j;
   cout<<"**************利用Prim算法得出的最小生成樹的邊如下**************"<<endl;
   cout<<"輸入時，如果兩點之間沒有連接邊請輸入一個比所有權值都大的數表示‘無窮大’"<<endl<<endl;
   cout<<"請輸入圖中節點的個數：";
   cin>>n;
   cout<<endl<<endl<<"你輸入的節點個數為：";
   cout<<"請輸入的圖中各邊的權值："<<endl;
   
   for(i=1;i<=n;i++)
    for(j=i+1;j<=n;j++)
	{
      cout<<"    邊("<<i<<"，"<<j<<")的權值：";
      cin>>c[i][j];
	}
	cout<<endl<<endl<<"**************<<""利用Prim算法得出的最小生成樹的邊如下**************"<<endl;
    prim();
	getch();
 
}