Kruskal’s algorithm is a minimum-spanning-tree algorithm where the algorithm finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph at each step.
//To Construct the minimum spanning tre for a graph using Kruskal's Algorithm
import java.io.*;
class edge {
int u, v, cost;
}
class kruskal {
edge E[];
int n, t[][], p[], e;
void getdata() throws IOException {
BufferedReader o = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter number of vertices: ");
n = Integer.parseInt(o.readLine());
System.out.println("Enter number of Edges: ");
e = Integer.parseInt(o.readLine());
E = new edge[20];
t = new int[n][3];
p = new int[n + 1];
for (int i = 1; i <= n; i++)
p[i] = -1;
for (int i = 1; i <= e; i++) {
edge x = new edge();
System.out.print("Source " + i + ":-\t");
x.u = Integer.parseInt(o.readLine());
System.out.print("Destin " + i + ":-\t");
x.v = Integer.parseInt(o.readLine());
System.out.print("Weight " + i + ":-\t");
x.cost = Integer.parseInt(o.readLine());
E[i] = x;
System.out.println();
}
}
void sort() {
edge t = new edge();
for (int i = 1; i <= e - 1; i++)
for (int j = 1; j <= e - i; j++)
if (E[j].cost > E[j + 1].cost) {
t = E[j];
E[j] = E[j + 1];
E[j + 1] = t;
}
System.out.println("The sorted array is: ");
for (int i = 1; i <= e; i++)
System.out.println("An edge is :(" + E[i].u + "," + E[i].v + ") and cost :" + E[i].cost);
}
void union(int i, int j) {
p[i] = j;
}
int find(int i) {
while (p[i] > 0)
i = p[i];
return i;
}
int greedykruskal() {
int mincost, u, v, min, j, k;
int i = 1;
int q = 1;
mincost = 0;
System.out.println("Edges selected are: ");
while (i <= n - 1) {
u = E[q].u;
v = E[q].v;
min = E[q].cost;
j = find(u);
k = find(v);
if (j != k) {
mincost = mincost + min;
t[i][1] = u;
t[i][2] = v;
System.out.println("An edge(" + u + "," + v + ") with cost:" + min);
i++;
union(j, k);
}
q++;
}
if (i <= n - 1) {
System.out.println("A spanning tree cannot be formed ");
return 0;
} else
return mincost;
}
}
class testkruskal {
public static void main(String args[]) throws IOException {
kruskal ob = new kruskal();
ob.getdata();
ob.sort();
int m = ob.greedykruskal();
System.out.println("Minimum cost is : " + m);
}
}
/*-----------------------------------OUTPUT-------------------------
Enter number of vertices: 5
Enter number of Edges: 7
Source 1:- 1
Destin 1:- 3
Weight 1:- 13
Source 2:- 1
Destin 2:- 5
Weight 2:- 2
Source 3:- 1
Destin 3:- 2
Weight 3:- 11
Source 4:- 2
Destin 4:- 3
Weight 4:- 15
Source 5:- 2
Destin 5:- 4
Weight 5:- 8
Source 6:- 2
Destin 6:- 5
Weight 6:- 12
Source 7:- 4
Destin 7:- 5
Weight 7:- 14
The sorted array is:
An edge is :(1,5) and cost :2
An edge is :(2,4) and cost :8
An edge is :(1,2) and cost :11
An edge is :(2,5) and cost :12
An edge is :(1,3) and cost :13
An edge is :(4,5) and cost :14
An edge is :(2,3) and cost :15
Edges selected are:
An edge(1,5) with cost:2
An edge(2,4) with cost:8
An edge(1,2) with cost:11
An edge(1,3) with cost:13
Minimum cost is : 34
Process Exit...
*/