C++ program for MST using Kruskal algorithm

C++ program for MST using Kruskal algorithm

#include <iostream>

using namespace std;

int find(int);

int uni(int,int);

int parent[9];

int main()

{

      int i,j,a,b,u,v,n,count=1;

      int min,mincost=0,cost[9][9];

      cout<<"\nEnter the number of nodes:";

      cin>>n;

      cout<<"\nEnter the adjacency matrix:\n";

      for(i=0;i<n;i++)

      {

            for(j=0;j<n;j++)

            {

                  cin>>cost[i][j];

                  if(cost[i][j]==0)

                        cost[i][j]=999;

            }

      }

      while(count < n)

      {

            min=999;

            for(i=0;i<n;i++)

            {

                  for(j=0;j < n;j++)

                  {

                        if(cost[i][j] < min)

                        {

                              min=cost[i][j];

                              a=u=i;

                              b=v=j;

                        }

                  }

            }

            u=find(u);

            v=find(v);

            if(uni(u,v))

            {

                  cout<<"\nEdge"<<count++ <<" : " <<a<<"->"<<b<<" Cost= "<<min;

                  mincost +=min;

            }

            cost[a][b]=cost[b][a]=999;

      }

      cout<<"\nMinimun cost="<<mincost;

      return 0;

}

int find(int i)

{

      while(parent[i])

            i=parent[i];

      return i;

}

int uni(int i,int j)

{

      if(i!=j)

      {

            parent[j]=i;

            return 1;

      }

      return 0;

}

output:

Enter the number of nodes:4

Enter the adjacency matrix:

0 5 1 4

0 0 0 3

0 2 0 0

0 0 3 0

Edge1 : 0->2 Cost= 1

Edge2 : 2->1 Cost= 2

Edge3 : 1->3 Cost= 3

Minimun cost=6