Monday, 3 November 2014

Minimum Spanning Tree Prim's Algorithm C++ code

#define INFINITY 0
#define MAXEDGE 15
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
void node(int i);
using namespace std;
int n,y=-1,arr[10];
struct group
{
   char name;
   int use;
}ob[MAXEDGE];
int main()
{
    int i,j,d,c1,c2,minimum,x,cnt;
    cout<<"\nEnter the number of nodes:";
    cin>>n;
    fflush(stdin);
    int adj[n][n];
    for(i=0;i<n;i++)
   {
    cout<<"\n\a\aEnter the name on node:";
    cin>>ob[i].name;
    ob[i].use=0;
    for(j=0;j<n;j++)
    {
         fflush(stdin);
         cout<<"\n\nEnter cost at position ("<<i+1<<","<<j+1<<") : ";
         cin>>adj[i][j];
    }
   }
    system("cls");
    cout<<"\nThe adjacency matrix::\n\n";
    cout<<" ";
    for(i=0;i<n;i++)
    {
        cout<<"  ";
        cout<<ob[i].name;
    }
    cout<<endl;
    for(i=0;i<n;i++)
    {
        cout<<ob[i].name<<" ";
        for(j=0;j<n;j++)
        {
           cout<<adj[i][j];
           cout<<"   ";
        }
        cout<<endl;
    }
cout<<"\n\n";
system("pause");
system("cls");
//DISPLAYDISPLAYDISPLAYDISPLAYDISPLAYDISPLAYDISPLAYDISPLAYDISPLAYDISPLAYDISPLAYDISPLAYDISPLAYDISPLAY
cout<<"MST vertex set          partial MST set                 chosen edge\n\n";
node(0);
for(i=0;i<n-1;i++)
{
    d=0;
    cnt=0;
    for(int q=0;q<23-(2*(i+1));q++)
    cout<<" ";
    for(x=0;x<=y;x++)
    for(j=0;j<n;j++)
    {
        if(adj[arr[x]][j]!=INFINITY && (ob[arr[x]].use==0 || ob[j].use==0))
        {
            if(d++==0)
            {
            minimum=adj[arr[x]][j];
            c1=arr[x];
            c2=j;
            }
            cout<<"("<<ob[arr[x]].name<<","<<ob[j].name<<")"<<",";
            cnt++;
            if(adj[arr[x]][j]<minimum)
            {
                minimum=adj[arr[x]][j];
                c1=arr[x];
                c2=j;
            }
        }
    }
    for(int q=0;q<32-(6*cnt);q++)
    cout<<" ";
    cout<<"("<<ob[c1].name<<","<<ob[c2].name<<")";
    node(c2);
}
return 0;
}
void node(int i)
{
    arr[++y]=i;
    ob[i].use=1;
    cout<<"\n\n{";
    for(int j=0;j<=y;j++)
    {
        cout<<ob[arr[j]].name;
        if(j!=y)
        cout<<",";
    }
    cout<<"}";
}

No comments:

Post a Comment