/*
source:  https://www.thecrazyprogrammer.com/2014/03/kruskals-algorithm-for-finding-minimum-cost-spanning-tree.html
*/

#include<stdio.h>

typedef struct edge
{
  int u,v,w;
} edge;
 
void kruskal(int *g, int n, edge mst[]);
int find(int belongs[],int vertexno);
void union1(int belongs[],int n, int c1,int c2);
void sort(edge elist[], int m);
void print(edge elist[], int m);

int main()
{
  int n = 6;
  //graph by adjacent matrix in 1D array
  int g[] = {
  0,3,1,6,0,0,
  3,0,5,0,3,0,
  1,5,0,5,6,4,
  6,0,5,0,0,2,
  0,3,6,0,0,6,
  0,0,4,2,6,0  
  };
  
  edge mst[n-1];
  kruskal(g, n, mst);
  print(mst, n-1);
  return 0;
}
 
void kruskal(int *g, int n, edge mst[])
{    
  //compute the number of edges
  int i, m = 0;  
    for (i=0; i< n*n; i++) {
     if (*(g+i) != 0) 
       m++;
  }
  m /= 2;  
  
  //create edge list of all edges  
  edge elist[m];
  int j, k = 0;
  for(i=1;i<n;i++) {
    for(j=0;j<i;j++)
    {
      if(*(g+i*n+j)!=0)
      {
        elist[k].u=i;
        elist[k].v=j;
        elist[k].w=*(g+i*n+j);
        k++;
      }
    }
  }
  
  //sort all edges
  sort(elist, m);
    
  //set initial components 
  int belongs[n], c1, c2;
  for(i=0;i<n;i++) belongs[i] = i;
  
  //start kruskal
  k = 0;
  for(i=0; i<m; i++)
  {
    c1=find(belongs, elist[i].u);
    c2=find(belongs, elist[i].v);
    if(c1!=c2) //if the two ends are not in the same component
    {
      mst[k]=elist[i];
      k++;
      union1(belongs, n, c1,c2);
    }
    if (k >= n-1) break; //break when the number of added edges reaches to n-1
  }
}

//find the component/subset the vertex belongs to.  
int find(int belongs[],int vertex)
{
  return(belongs[vertex]);
}

//union of two components, not the most efficient implmentation 
void union1(int belongs[],int n, int c1, int c2)
{
  int i;
  for(i=0;i<n;i++)
    if(belongs[i]==c2)
       belongs[i]=c1;
}
 
//bubble sort
void sort(edge elist[], int m) 
{
  int i,j;
  edge temp;
  for(i=1;i<m;i++)
     for(j=0;j< m-1;j++)
       if(elist[j].w >elist[j+1].w)
       {
         temp=elist[j];
         elist[j] = elist[j+1];
         elist[j+1]=temp;
       }
}
 
void print(edge elist[], int m)
{
  int i,cost=0;
  for(i=0;i<m;i++)
  {
    printf("\n(%d\t%d\t%d)",elist[i].u, elist[i].v, elist[i].w);
    cost +=elist[i].w;
  } 
  printf("\n\nCost of the spanning tree=%d",cost);
}

/*
(2      0       1)
(5      3       2)
(1      0       3)
(4      1       3)
(5      2       4)

Cost of the spanning tree=13
*/