JAVA program for creating a minimum spanning tree using Kruskal's algorithm for Shortest Path

JAVA program for creating a minimum spanning tree using Kruskal's algorithm for Shortest Path

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>

struct edge
{
    int u;
    int v;
    int weight;
    struct edge *link;
};

class kruskals
{
private:
    struct edge *front,tree[20];
    int father[20],n,wt_tree,count;
public:
    kruskals()
    {
       front=NULL;
       wt_tree=0;
       count=0;
       cout<<"Enter total no. of nodes in graph : ";
       cin>>n;
    }
    void create_graph();
    void make_tree();
    void insert_tree(int i,int j, int wt);
    void insert_priorityQ(int i,int j,int wt);
    struct edge *del_priorityQ();
    void display();
};

void kruskals::create_graph()
{
    int wt,max_edges,origin,destin;
    max_edges=n*(n-1)/2;
    for(int i=1;i<=max_edges;i++)
    {
        cout<<"Enter edge "<<i<<" (0 0 to quit) : ";
        cin>>origin>>destin;
        if((origin==0)&&(destin==0))
              break;
        cout<<"Enter weight of this edge : ";
        cin>>wt;
        if(origin>n || destin>n || origin<=0 || destin<=0)
        {
            cout<<"Invalid edge! "<<endl;
            i--;
        }
        else
        insert_priorityQ(origin,destin,wt);
    }
    if(i<n-1)
    {
        cout<<"Spanning tree is not possible "<<endl;
                getch();
        exit(1);
    }
}

void kruskals::make_tree()
{
    struct edge *temp;
    int node1,node2, root_n1,root_n2;

    while(count<n-1)
    {
        for(int i=0;i<20;i++)
                      father[i]=NULL;
        temp=del_priorityQ();
        node1=temp->u;
        node2=temp->v;
        cout<<endl<<"n1="<<node1<<"    "<<"n2="<<node2<<"     ";
        while(node1>0)
        {
             root_n1=node1;
             node1=father[node1];
        }
        while(node2>0)
        {
             root_n2=node2;
             node2=father[node2];
        }
        cout<<"rootn1="<<root_n1<<"     "<<"rootn2="<<root_n2<<endl;

        if(root_n1 != root_n2)
        {
              insert_tree(temp->u,temp->v,temp->weight);
              wt_tree=wt_tree+temp->weight;
              father[root_n2]=root_n1;
        }
    }
}

void kruskals::insert_tree(int i, int j, int wt)
{
    cout<<"This edge inserted in the spanning tree "<<endl;
    count++;
    tree[count].u=i;
    tree[count].v=j;
    tree[count].weight=wt;
}

void kruskals::insert_priorityQ(int i, int j, int wt)
{
    struct edge *temp,*q;

    temp=new edge;
    temp->u=i;
    temp->v=j;
    temp->weight=wt;

    if(front==NULL || temp->weight<front->weight)
    {
        temp->link =front;
        front=temp;
    }
    else
    {
        q=front;
        while(q->link !=NULL && q->link->weight<=temp->weight)
              q=q->link;
        temp->link=q->link;
        q->link=temp;
        if(q->link==NULL)
               temp->link=NULL;
    }
}

struct edge* kruskals::del_priorityQ()
{
    struct edge *temp;
    temp=front;
    cout<<"Edge processed is "<<temp->u<<"->"<<temp->v<<":"<<temp->weight;
    front=front->link;
    return temp;
}

void kruskals::display()
{
    cout<<"Edges to be included in spanning tree are : "<<endl;
    for(int i=1;i<=count;i++)
    {
       cout<<"("<<tree[i].u<<" ";
       cout<<tree[i].v<<")   ";
    }
    cout<<endl
        <<"Weight of this minimum spanning tree is : " <<wt_tree;
}

void main()
{
clrscr();
kruskals k;
k.create_graph();
k.make_tree();
k.display();
getch();
}