/*分別利用prim算法和kruskal算法實現求圖的最小生成樹*/
#include<stdio.h>
#include<stdlib.h>
#define MaxVertexNum  12
#define MaxEdgeNum 20
#define MaxValue 1000
typedef int Vertextype;
typedef int adjmatrix[MaxVertexNum][MaxVertexNum];
typedef Vertextype vexlist[MaxVertexNum];
int visited[MaxVertexNum]={0};

struct edgeElem
{int fromvex;
 int endvex;
 int weight;
};
typedef struct edgeElem edgeset[MaxVertexNum]; 


void Creat_adjmatrix(vexlist GV,adjmatrix GA,int n,int e)
{int i,j,k,w;
 printf("輸入%d個頂點數據",n);
 for(i=0;i<n;i++)
   scanf("%d",&GV[i]);
 for(i=0;i<n;i++)
   for(j=0;j<n;j++)
        if(i==j) GA[i][j]=0;
         else GA[i][j]=MaxValue;
 printf("輸入%d條無向帶權邊",e);
 for(k=0;k<e;k++)
 {
 scanf("%d%d%d",&i,&j,&w);
 GA[i][j]=GA[j][i]=w;
 }

}

 

void Creat_edgeset(vexlist GV,edgeset GE,int n,int e)
{int i,j,k,w;
 printf("輸入%d個頂點數據",n);
 for(i=0;i<n;i++)
   scanf("%d",&GV[i]);
printf("輸入%d條無向帶權邊",e);
 for(k=0;k<e;k++)
 { scanf("%d%d%d",&i,&j,&w);
   GE[k].fromvex=i;
   GE[k].endvex=j;
   GE[k].weight=w;
 }
}

 

void output_edgeset(edgeset GE,int e)
{int k;
for(k=0;k<e;k++)
 printf("%d %d %d,",GE[k].fromvex,GE[k].endvex,GE[k].weight);
 printf("\n");
}

 


void prim(adjmatrix GA,edgeset CT,int a,int n)
{int i,j,t,k,w,min,m;
 struct edgeElem x;
 for(i=0;i<n;i++)
 if(i<a)
   {CT[i].fromvex=a;
    CT[i].endvex=i;
    CT[i].weight=GA[a][i];
   }
 else if(i>a)
   {CT[i-1].fromvex=a;
    CT[i-1].endvex=i;
    CT[i-1].weight=GA[a][i];
    }
for(k=1;k<n;k++)
  {
    min=MaxValue;
    m=k-1;
    for(j=k-1;j<n-1;j++)
      if(CT[j].weight<min){min=CT[j].weight;m=j;}
      x=CT[k-1];CT[k-1]=CT[m];CT[m]=x;
    j=CT[k-1].endvex;
   for(i=k;i<n-1;i++)
{t=CT[i].endvex;w=GA[j][t];
   if(w<CT[i].weight)
     {CT[i].weight=w;
      CT[i].fromvex=j;
      }
    }
}
}  

 


void kruskal(edgeset GE,edgeset C,int n)
 { int i,j,k,d;
    int m1,m2;
    adjmatrix s;
  for(i=0;i<n;i++)
    {for(j=0;j<n;j++)
       if(i==j) s[i][j]=1;else s[i][j]=0;
     }
 k=1;
d=0;
while(k<n)
{  
  for(i=0;i<n;i++)
   {if(s[i][GE[d].fromvex]==1) m1=i;
    if(s[i][GE[d].endvex]==1) m2=i;
}

if(m1!=m2)
{C[k-1]=GE[d];k++;
for(j=0;j<n;j++)
{s[m1][j]=s[m1][j]||s[m2][j];
 s[m2][j]=0;
 }
}
d++;
}
}

 

void main()
{int n,e;
 vexlist GV;
 adjmatrix GA;
 edgeset GE,C;
 printf("輸入圖的頂點數和邊數：");
 scanf("%d%d",&n,&e);
 Creat_adjmatrix( GV, GA, n, e);
 printf("利用prim算法從0點出發求圖的最小生成樹：\n");
 prim(GA,GE,0,n);
 output_edgeset( GE, n-1);
 printf("輸入圖的頂點數和邊數:");
 scanf("%d%d",&n,&e);
 Creat_edgeset( GV,GE,n, e);
 printf("利用kruskal算法從0點出發求圖的最小生成樹：\n");
 kruskal( GE, C, n);
 output_edgeset( C, n-1);

}