prims algo

#include<iostream.h>

class prims
{
private:
    int n;
    int graph_edge[250][4];
    int g;
    int tree_edge[250][4];
    int t;
    int s;


    int T1[50],t1;
    int T2[50],t2;

public:
    void input();
    int findset(int);
    void algorithm();
    void output();
};
void prims::input()
{
    cout<<"Enter the no. of nodes in the undirected weighted graph\n";
    cin>>n;

    g=0;

    cout<<"Enter the weights for the following edges\n";
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            cout<<" < "<<i<<" , "<<j<<" > ";
            int w;
            cin>>w;
            if(w!=0)
            {
                g++;

                graph_edge[g][1]=i;
                graph_edge[g][2]=j;
                graph_edge[g][3]=w;
            }
        }
    }



    cout<<"\n\nThe edges in the given graph are:\n";
    for(i=1;i<=g;i++)
    cout<<" < "<<graph_edge[i][1]<<" , "<<graph_edge[i][2]<<" > :"<<graph_edge[i][3]<<endl;
}

int prims::findset(int x)
{
    for(int i=1;i<=t1;i++)
        if(x==T1[i])
            return 1;

    for(i=1;i<=t2;i++)
        if(x==T2[i])
            return 2;
        return -1;
}

void prims::algorithm()
{
    t=0;

    t1=1;
    T1[1]=1;

    t2=n-1;
    int i;
    for(i=1;i<=n-1;i++)
        T2[i]=i+1;
    while(g!=0 && t!=n-1)
    {

        int min=9999;
        int p;
        int u,v,w;
        for(i=1;i<=g;i++)
        {
            bool flag1=false,flag2=false;


            if(findset(graph_edge[i][1])!=findset(graph_edge[i][2]))
            {
                if(min>graph_edge[i][3])
                {
                    min=graph_edge[i][3];
                    u=graph_edge[i][1];
                    v=graph_edge[i][2];
                    w=graph_edge[i][3];

                    p=i;
                }
            }
        }



        cout<<"The edge included in the tree is :";
        cout<<" < "<<u<<" , "<<v<<" > "<<endl;



        for(int l=p;l<g;l++)
        {
            graph_edge[l][1]=graph_edge[l+1][1];
            graph_edge[l][2]=graph_edge[l+1][2];
            graph_edge[l][3]=graph_edge[l+1][3];
        }
        t++;
        tree_edge[t][1]=u;
        tree_edge[t][2]=v;
        tree_edge[t][3]=w;


        t1++;

        int m;
        if(findset(v)==2)
        {
            T1[t1]=v;
            m=v;
        }
        else
            if(findset(u)==2)
            {
                T1[t1]=u;
                m=u;
            }

        int x;
        for(x=1;T2[x]!=m;x++);
            for(;x<t2;x++)
                T2[x]=T2[x+1];
        int k;
        cout<<"NOW\nT1 :: ";
        for(k=1;k<=t1;k++)
            cout<<T1[k]<<"  ";
        cout<<endl;

        cout<<"T2 :: ";
        for(k=1;k<=t2;k++)
            cout<<T2[k]<<" ";
        cout<<endl;

        cout<<"The graph edges are ::\n";
        for(i=1;i<=g;i++)
            cout<<" < "<<graph_edge[i][1]<<" , "<<graph_edge[i][2]<<" > ::"<<graph_edge[i][3]<<endl;

        cout<<endl<<endl;

    }
}

void prims::output()
{
    cout<<"\nThe selected edges are ::\n";
    for(int i=1;i<=t;i++)
        cout<<" < "<<tree_edge[i][1]<<" , "<<tree_edge[i][2]<<" > ::"<<tree_edge[i][3]<<endl;
}
int main()
{
    prims obj;
    obj.input();
    obj.algorithm();
    obj.output();
    return 0;
}

OUTPUT:
Enter the no. of nodes in the undirected weighted graph
6
Enter the weights for the following edges
 < 1 , 2 > 12
 < 1 , 3 > 0
 < 1 , 4 > 0
 < 1 , 5 > 15
 < 1 , 6 > 17
 < 2 , 3 > 1
 < 2 , 4 > 2
 < 2 , 5 > 0
 < 2 , 6 > 3
 < 3 , 4 > 6
 < 3 , 5 > 0
 < 3 , 6 > 0
 < 4 , 5 > 14
 < 4 , 6 > 10
 < 5 , 6 > 19


The edges in the given graph are:
 < 1 , 2 > :12
 < 1 , 5 > :15
 < 1 , 6 > :17
 < 2 , 3 > :1
 < 2 , 4 > :2
 < 2 , 6 > :3
 < 3 , 4 > :6
 < 4 , 5 > :14
 < 4 , 6 > :10
 < 5 , 6 > :19
The edge included in the tree is : < 1 , 2 >
NOW
T1 :: 1  2
T2 :: 3 4 5 6 6
The graph edges are ::
 < 1 , 5 > ::15
 < 1 , 6 > ::17
 < 2 , 3 > ::1
 < 2 , 4 > ::2
 < 2 , 6 > ::3
 < 3 , 4 > ::6
 < 4 , 5 > ::14
 < 4 , 6 > ::10
 < 5 , 6 > ::19
 < 5 , 6 > ::19


The edge included in the tree is : < 2 , 3 >
NOW
T1 :: 1  2  3
T2 :: 4 5 6 6 6
The graph edges are ::
 < 1 , 5 > ::15
 < 1 , 6 > ::17
 < 2 , 4 > ::2
 < 2 , 6 > ::3
 < 3 , 4 > ::6
 < 4 , 5 > ::14
 < 4 , 6 > ::10
 < 5 , 6 > ::19
 < 5 , 6 > ::19
 < 5 , 6 > ::19


The edge included in the tree is : < 2 , 4 >
NOW
T1 :: 1  2  3  4
T2 :: 5 6 6 6 6
The graph edges are ::
 < 1 , 5 > ::15
 < 1 , 6 > ::17
 < 2 , 6 > ::3
 < 3 , 4 > ::6
 < 4 , 5 > ::14
 < 4 , 6 > ::10
 < 5 , 6 > ::19
 < 5 , 6 > ::19
 < 5 , 6 > ::19
 < 5 , 6 > ::19


The edge included in the tree is : < 2 , 6 >
NOW
T1 :: 1  2  3  4  6
T2 :: 5 6 6 6 6
The graph edges are ::
 < 1 , 5 > ::15
 < 1 , 6 > ::17
 < 3 , 4 > ::6
 < 4 , 5 > ::14
 < 4 , 6 > ::10
 < 5 , 6 > ::19
 < 5 , 6 > ::19
 < 5 , 6 > ::19
 < 5 , 6 > ::19
 < 5 , 6 > ::19


The edge included in the tree is : < 4 , 5 >
NOW
T1 :: 1  2  3  4  6  5
T2 :: 6 6 6 6 6
The graph edges are ::
 < 1 , 5 > ::15
 < 1 , 6 > ::17
 < 3 , 4 > ::6
 < 4 , 6 > ::10
 < 5 , 6 > ::19
 < 5 , 6 > ::19
 < 5 , 6 > ::19
 < 5 , 6 > ::19
 < 5 , 6 > ::19
 < 5 , 6 > ::19



The selected edges are ::
 < 1 , 2 > ::12
 < 2 , 3 > ::1
 < 2 , 4 > ::2
 < 2 , 6 > ::3
 < 4 , 5 > ::14
Press any key to continue