The Minimum Spanning Tree (MST) problem is a classic and fundamental topic in graph theory and algorithms. In this blog post, we will demonstrate how to implement Kruskal’s Algorithm in Java to construct a minimum spanning tree for a given graph.
What is a Minimum Spanning Tree?
A spanning tree of a graph is a subgraph that connects all the vertices together without any cycles and with the minimum possible number of edges (which is V-1 for a graph with V vertices).
A Minimum Spanning Tree (MST) is a spanning tree where the sum of the weights of the included edges is minimized.
How Kruskal’s Algorithm Works
Kruskal’s algorithm is a greedy algorithm that operates by always choosing the smallest available edge that connects two separate trees in the growing forest until a spanning tree is formed.
Here’s how it works:
- Sort all edges: Begin by sorting all the edges in non-decreasing order of their weights.
- Pick the smallest edge: Select the smallest edge and check if it forms a cycle with the spanning tree formed so far.
- If no cycle is formed, include it: Use a union-find (disjoint-set) structure to keep track of connected components and ensure no cycles are introduced.
- Repeat: Continue adding edges until there are
V-1edges in the spanning tree.
Java Code Implementation
Below is a Java implementation of Kruskal’s Algorithm using an edge list, sorting, and a union-find technique.
import java.io.*;
// Class representing an edge in the graph
class Edge {
int u, v, cost; // u and v are the connected vertices, cost is the edge weight
}
class Kruskal {
Edge E[]; // Array of edges
int n, e, t[][], p[]; // n = number of vertices, e = number of edges, t = MST edges, p = parent array for union-find
// Step 1: Get graph data from the user
void getData() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter number of vertices: ");
n = Integer.parseInt(br.readLine());
System.out.print("Enter number of Edges: ");
e = Integer.parseInt(br.readLine());
E = new Edge[20];
t = new int[n][3];
p = new int[n + 1];
// Initialize disjoint set parent array
for (int i = 1; i <= n; i++)
p[i] = -1;
// Input each edge's details
for (int i = 1; i <= e; i++) {
Edge x = new Edge();
System.out.print("Source " + i + ":- ");
x.u = Integer.parseInt(br.readLine());
System.out.print("Destination " + i + ":- ");
x.v = Integer.parseInt(br.readLine());
System.out.print("Weight " + i + ":- ");
x.cost = Integer.parseInt(br.readLine());
E[i] = x;
System.out.println();
}
}
// Step 2: Sort edges by weight using bubble sort
void sort() {
Edge temp;
for (int i = 1; i <= e - 1; i++)
for (int j = 1; j <= e - i; j++)
if (E[j].cost > E[j + 1].cost) {
temp = E[j];
E[j] = E[j + 1];
E[j + 1] = temp;
}
System.out.println("Sorted edges by cost:");
for (int i = 1; i <= e; i++)
System.out.println("Edge (" + E[i].u + "," + E[i].v + ") with cost: " + E[i].cost);
}
// Union operation for union-find
void union(int i, int j) {
p[i] = j;
}
// Find operation with path tracing
int find(int i) {
while (p[i] > 0)
i = p[i];
return i;
}
// Step 3 and 4: Function implementing Kruskal's greedy approach
int greedyKruskal() {
int mincost = 0, u, v, j, k, min;
int i = 1, q = 1;
System.out.println("Edges selected are:");
// Repeat: Keep selecting edges until MST has (n-1) edges
while (i <= n - 1) {
u = E[q].u;
v = E[q].v;
min = E[q].cost;
j = find(u); // Find parent set of u
k = find(v); // Find parent set of v
// If no cycle is formed (different sets), include this edge
if (j != k) {
mincost += min;
t[i][1] = u;
t[i][2] = v;
System.out.println("Edge (" + u + "," + v + ") with cost: " + min);
i++;
union(j, k); // Union the sets
}
q++;
}
// Completion: If not enough edges for MST
if (i <= n - 1) {
System.out.println("A spanning tree cannot be formed");
return 0;
} else
return mincost;
}
}
public class TestKruskal {
public static void main(String[] args) throws IOException {
Kruskal ob = new Kruskal();
ob.getData(); // Step 1: Input graph data
ob.sort(); // Step 2: Sort edges by cost
int cost = ob.greedyKruskal(); // Step 3 & 4: Apply Kruskal's Algorithm
System.out.println("Minimum cost of spanning tree: " + cost);
}
}
Sample Output
Enter number of vertices: 5
Enter number of Edges: 7
Source 1:- 1
Destination 1:- 3
Weight 1:- 13
Source 2:- 1
Destination 2:- 5
Weight 2:- 2
Source 3:- 1
Destination 3:- 2
Weight 3:- 11
Source 4:- 2
Destination 4:- 4
Weight 4:- 8
Source 5:- 3
Destination 5:- 4
Weight 5:- 7
Source 6:- 3
Destination 6:- 5
Weight 6:- 15
Source 7:- 4
Destination 7:- 5
Weight 7:- 9
Sorted edges by cost:
Edge (1,5) with cost: 2
Edge (3,4) with cost: 7
Edge (2,4) with cost: 8
Edge (4,5) with cost: 9
Edge (1,2) with cost: 11
Edge (1,3) with cost: 13
Edge (3,5) with cost: 15
Edges selected are:
Edge (1,5) with cost: 2
Edge (3,4) with cost: 7
Edge (2,4) with cost: 8
Edge (1,2) with cost: 11
Minimum cost of spanning tree: 28Step-by-Step Output Explanation
Input Phase: User inputs the graph with 5 vertices and 7 edges along with their weights.
Sorting Phase: Edges are sorted in non-decreasing order based on weights.
Greedy Selection Phase:
- Edge (1,5) is chosen first as it has the lowest cost.
- Edge (3,4) is added next.
- Edge (2,4) is included.
- Edge (1,2) is added.
Completion: Once 4 edges (for 5 vertices, V-1=4) are added without forming a cycle, MST is complete.
Total Cost Calculation: The total cost of the selected edges is computed as 2 + 7 + 8 + 11 = 28.