kruskal.cpp

kruskal algo is a sorting algo

#include<iostream.h>
#include<conio.h>
class kruskal
{
private:
 int n;
 int graph[10][10];
 int tree[10][10];
 int noe;
 int edges[100][4];
 int sets[100][10];
 int top[100];
public:
 void read_graph();
 void initialize_span_t();
 void sort_edges();
 void algorithm();
 int find_node(int );
 void print_min_span_t();
};

void kruskal::read_graph()
{
 cout<<"Enter the no. of nodes in the graph ::";
 cin>>n;
 cout<<"Enter the adjacency matrix of the graph ::\n";
 for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
   cin>>graph[i][j];
}

void kruskal::sort_edges()
{
 int i,j;
 /******* Initialize the edges *************/
 noe=0;
 for(i=1;i<=n;i++)
 {
  for(j=i;j<=n;j++)
  {
   if(graph[i][j]!=0)
   {
    noe++;
    edges[noe][1]=i;
    edges[noe][2]=j;
    edges[noe][3]=graph[i][j];
   }
  }
 }
 
 /*********** Sort the edges **************/
 
 for(i=1;i<=noe;i++)
 {
  for(j=i;j<=noe-1;j++)
  {
   if(edges[j][3]>edges[j+1][3])
   {
    int t=edges[j][1];
    edges[j][1]=edges[j+1][1];
    edges[j+1][1]=t;
    
    t=edges[j][2];
    edges[j][2]=edges[j+1][2];
    edges[j+1][2]=t;
    
    t=edges[j][3];
    edges[j][3]=edges[j+1][3];
    edges[j+1][3]=t;
   }
  }
 }
  
  /*********** Print the edges **************/

 cout<<endl;
 for(i=1;i<=noe;i++)
  cout<<edges[i][1]<<"\t"<<edges[i][2]<<"\t"<<edges[i][3]<<endl;
}

void kruskal::initialize_span_t()
{
 for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
   tree[i][j]=0;
}

void kruskal::algorithm()
{
 // ->make a set for each node
 for(int i=1;i<=n;i++)
 {
  sets[i][1]=i;
  top[i]=1;
 }

 for(int i=1;i<=noe;i++)
 {
  int p1=find_node(edges[i][1]);
  int p2=find_node(edges[i][2]);

  cout<<p1<<"\t"<<p2<<endl;

  if(p1!=p2)
  {
   tree[edges[i][1]][edges[i][2]]=edges[i][3];
   tree[edges[i][2]][edges[i][1]]=edges[i][3];

   // Mix the two sets
   
   for(int j=1;j<=top[p2];j++)
   {
    top[p1]++;
    sets[p1][top[p1]]=sets[p2][j];
   }

   top[p2]=0;
  }
 }
}

int kruskal::find_node(int n)
{
 for(int i=1;i<=noe;i++)
 {
  for(int j=1;j<=top[i];j++)
  {
   if(n==sets[i][j])
    return i;
  }
 }
 return -1;
}
void kruskal::print_min_span_t()
{
 for(int i=1;i<=n;i++)
 {
  for(int j=1;j<=n;j++)
   cout<<tree[i][j]<<"\t";
  cout<<endl;
 }
}
int main()
{
 kruskal obj;
 obj.read_graph();
 obj.sort_edges();
 obj.initialize_span_t();
 obj.algorithm();
 obj.print_min_span_t();
 
 getch();
 return 0;
}