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();
}
