To implement Kruskal’s algorithm.

import java.io.*;
import java.util.*;
class Graph
{

int i,n; //no of nodes
int noe; //no edges in the graph
int graph_edge[][]=new int[100][4];
int tree[][]=new int [10][10];
int sets[][]=new int[100][10];
int top[]=new int[100];
int cost=0;

int getNumber()
{
String str;
int ne=0;
InputStreamReader input=new InputStreamReader(System.in);
BufferedReader in=new BufferedReader(input);
try
{
str=in.readLine();
ne=Integer.parseInt(str);
}
catch(Exception e)
{
System.out.println("I/O Error");
}
return ne;
}/*end getNumber*/

void read_graph()
{
System.out.print("Enter the no. of nodes in the undirected weighted graph ::");
n=getNumber();

noe=0;

System.out.println("Enter the weights for the following edges ::\n");
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
System.out.print(" < "+i+" , "+j+" > ::");
int w;
w=getNumber();
if(w!=0)
{
noe++;
graph_edge[noe][1]=i;
graph_edge[noe][2]=j;
graph_edge[noe][3]=w;
}
}
}
}

void sort_edges()
{
/**** Sort the edges using bubble sort in increasing order**************/

for(int i=1;i<=noe-1;i++)
{
for(int j=1;j<=noe-i;j++)
{
if(graph_edge[j][3]>graph_edge[j+1][3])
{
int t=graph_edge[j][1];
graph_edge[j][1]=graph_edge[j+1][1];
graph_edge[j+1][1]=t;

t=graph_edge[j][2];
graph_edge[j][2]=graph_edge[j+1][2];
graph_edge[j+1][2]=t;

t=graph_edge[j][3];
graph_edge[j][3]=graph_edge[j+1][3];
graph_edge[j+1][3]=t;
}
}
}
}

void algorithm()
{
// ->make a set for each node
for(int i=1;i<=n;i++)
{
sets[i][1]=i;
top[i]=1;
}

System.out.println("\nThe algorithm starts ::\n\n");

for(i=1;i<=noe;i++)
{
int p1=find_node(graph_edge[i][1]);
int p2=find_node(graph_edge[i][2]);

if(p1!=p2)
{
System.out.print("The edge included in the tree is ::");
System.out.print("< "+graph_edge[i][1]+" , ");
System.out.println(graph_edge[i][2]+" > ");;
cost=cost+graph_edge[i][3];

tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];
tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];

// Mix the two sets

for(int j=1;j<=top[p2];j++)
{
top[p1]++;
sets[p1][top[p1]]=sets[p2][j];
}
top[p2]=0;
}
else
{
System.out.println("Inclusion of the edge ");
System.out.print(" < "+graph_edge[i][1]+" , ");
System.out.println(graph_edge[i][2]+"> forms a cycle so it is removed\n\n");
}
}

System.out.println("Cost of the spanning tree : "+cost);
}

int find_node(int n)
{
for(int i=1;i<=noe;i++)
{
for(int j=1;j<=top[i];j++)
{
if(n==sets[i][j])
return i;
}
}
return -1;
}
}

class Kruskal1
{
public static void main(String args[])
{
Graph obj=new Graph();
obj.read_graph();
obj.sort_edges();
obj.algorithm();
}
}

/*
Enter the no. of nodes in the undirected weighted graph ::6
Enter the weights for the following edges ::

< 1 , 2 > ::3
< 1 , 3 > ::1
< 1 , 4 > ::6
< 1 , 5 > ::0
< 1 , 6 > ::0
< 2 , 3 > ::5
< 2 , 4 > ::0
< 2 , 5 > ::3
< 2 , 6 > ::0
< 3 , 4 > ::5
< 3 , 5 > ::6
< 3 , 6 > ::4
< 4 , 5 > ::0
< 4 , 6 > ::2
< 5 , 6 > ::6

The algorithm starts ::


The edge included in the tree is ::< 1 , 3 >
The edge included in the tree is ::< 4 , 6 >
The edge included in the tree is ::< 1 , 2 >
The edge included in the tree is ::< 2 , 5 >
The edge included in the tree is ::< 3 , 6 >
Inclusion of the edge
< 2 , 3> forms a cycle so it is removed


Inclusion of the edge
< 3 , 4> forms a cycle so it is removed


Inclusion of the edge
< 1 , 4> forms a cycle so it is removed


Inclusion of the edge
< 3 , 5> forms a cycle so it is removed


Inclusion of the edge
< 5 , 6> forms a cycle so it is removed


Cost of the spanning tree : 13
*/