Monday, 3 November 2014

Implementing Kruskal's Algorithm Data Structure C++ code

# define INFINITY 0
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
int n,y=-1,k,flag;
struct group
{
    int cost,e1,e2;
}ob[12];
int main()
{
    int i,j,m,b,c=0,sum=0;
    cout<<"\nEnter the number of nodes:";
    cin>>n;
    fflush(stdin);
    char name[n];
    int adj[n][n],test[n],path[n][n],path_copy[n][n];
    for(i=0;i<n;i++)
   {
     cout<<"\n\a\aEnter the name on node:";
     cin>>name[i];
    for(j=0;j<n;j++)
    {
         fflush(stdin);
         cout<<"\n\nEnter cost at position ("<<i+1<<","<<j+1<<") : ";
         cin>>adj[i][j];
         path[i][j]=0;
         path_copy[i][j]=0;
         if(j>i && adj[i][j]!=INFINITY)
         {
         ob[++y].cost=adj[i][j];
         ob[y].e1=i;
         ob[y].e2=j;
         }
    }
   }
    system("cls");
    cout<<"\nThe adjacency matrix::\n\n";
    cout<<" ";
    for(i=0;i<n;i++)
    {
        cout<<"  ";
        cout<<name[i];
    }
    cout<<endl;
    for(i=0;i<n;i++)
    {
        cout<<name[i]<<" ";
        for(j=0;j<n;j++)
        {
           cout<<adj[i][j];
           cout<<"   ";
        }
        cout<<endl;
    }
    system("pause");
    system("cls");
    //Sort(Selection)
    for(i=0;i<=y;i++)
    {
        k=0;
        for(j=1;j<=y-i;j++)
        {
            if((ob[j].cost)>(ob[k].cost))
            k=j;
        }
        swap(ob[k],ob[j-1]);
    }
    cout<<"\nCost             Edge\n\n";
    for(i=0;i<=y;i++)
    {
        m=0;b=0,flag=1;
        for(j=0;j<i;j++)
        {
            if(ob[i].e1==ob[j].e1 || ob[i].e1==ob[j].e2)
            {m++;}
            if(ob[i].e2==ob[j].e1 || ob[i].e2==ob[j].e2)
            {b++;}
        }
        if(m>0 && b>0 && c<n-1)
        {
            //Warshall
            int f,g,k;
            for(k=0;k<n;k++)
            {
                for(f=0;f<n;f++)
                {
                    for(g=0;g<n;g++)
                    {
                        if(path[f][k]*path[k][g]==1)
                        path[f][g]=1;
                    }
                }
            }
            if(path[ob[i].e1][ob[i].e2]==1)
            flag=0;

            else
            {
                path_copy[ob[i].e1][ob[i].e2]=1;
                path_copy[ob[i].e2][ob[i].e1]=1;
                //For restoring path matrix
                for(int u=0;u<n;u++)
                {
                    for(int v=0;v<n;v++)
                    path[u][v]=path_copy[u][v];
                }
            }
        }
        else
        {
            path[ob[i].e1][ob[i].e2]=1;
            path[ob[i].e2][ob[i].e1]=1;

            path_copy[ob[i].e1][ob[i].e2]=1;
            path_copy[ob[i].e2][ob[i].e1]=1;
        }
        if(flag==1 && c<n-1)
        {
            cout<<ob[i].cost<<"               "<<"("<<name[ob[i].e1]<<","<<name[ob[i].e2]<<")"<<endl<<endl;
            c++;
            sum+=ob[i].cost;
        }
    }
    cout<<"----\n"<<sum<<endl<<endl;
    return 0;
}

No comments:

Post a Comment