Hello! Today, we will learn about the Minimum Spanning Tree problem that frequently appears in algorithm exams. In particular, we will delve deeply into how to solve this problem using Java.
Problem Description
Let’s assume there is a weighted connected graph as follows. All vertices of this graph are connected, and the weights are different from each other. Your goal is to find the minimum spanning tree of this graph.
Input Format
- The first line contains the number of vertices
Vand the number of edgesE. - The next
Elines contain the two vertices and the weight of each edgeu,v,w.
Output Format
Print the list of edges that make up the minimum spanning tree and the total weight.
Example Input/Output
Example Input
3 3
1 2 1
2 3 2
1 3 3
Example Output
1 - 2
2 - 3
Total Weight: 3
Approach to Problem Solving
The representative algorithms used to find the minimum spanning tree are Kruskal’s Algorithm and Prim’s Algorithm. Here, we will use Kruskal’s Algorithm to solve this problem.
Overview of Kruskal’s Algorithm
- Sort the edges in ascending order based on weight.
- Select the edge with the smallest weight, and if it doesn’t form a cycle, include this edge in the result.
- Repeat the above process until all vertices are connected.
Java Code Implementation
Now, let’s implement Kruskal’s Algorithm through Java code.
import java.util.Arrays;
public class Kruskal {
static class Edge implements Comparable {
int u, v, weight;
Edge(int u, int v, int weight) {
this.u = u;
this.v = v;
this.weight = weight;
}
@Override
public int compareTo(Edge other) {
return this.weight - other.weight;
}
}
static int[] parent;
static int[] rank;
public static void main(String[] args) {
int V = 3; // Number of vertices
int E = 3; // Number of edges
Edge[] edges = new Edge[E];
edges[0] = new Edge(1, 2, 1);
edges[1] = new Edge(2, 3, 2);
edges[2] = new Edge(1, 3, 3);
Arrays.sort(edges);
parent = new int[V + 1];
rank = new int[V + 1];
for (int i = 1; i <= V; i++) {
parent[i] = i;
rank[i] = 0;
}
int totalWeight = 0;
System.out.println("Edges of the minimum spanning tree:");
for (Edge edge : edges) {
if (union(edge.u, edge.v)) {
System.out.println(edge.u + " - " + edge.v);
totalWeight += edge.weight;
}
}
System.out.println("Total Weight: " + totalWeight);
}
static int find(int u) {
if (parent[u] != u) {
parent[u] = find(parent[u]);
}
return parent[u];
}
static boolean union(int u, int v) {
int rootU = find(u);
int rootV = find(v);
if (rootU != rootV) {
if (rank[rootU] < rank[rootV]) {
parent[rootU] = rootV;
} else if (rank[rootU] > rank[rootV]) {
parent[rootV] = rootU;
} else {
parent[rootV] = rootU;
rank[rootU]++;
}
return true;
}
return false;
}
}
Code Explanation
The above code implements the following key functionalities:
- Edge Class: A class representing edges, set up to be comparable based on weight.
- find Method: Finds and returns the root node through the Union-Find algorithm. It improves performance using Path Compression.
- union Method: Combines the root nodes of two vertices if they are different and returns whether the union was successful. This helps to check for cycles.
Testing and Execution
When you compile and execute this code, the following results will be printed:
Edges of the minimum spanning tree:
1 - 2
2 - 3
Total Weight: 3
Applications of Minimum Spanning Trees
Minimum spanning trees can be applied in various fields. For example:
- Network Design: Useful in determining paths that can be connected at minimal cost when designing computer networks.
- Road Network Construction: Can be used for constructing urban road networks at minimal cost.
- Power Grid Design: Spanning tree algorithms are utilized for cost reduction in power grids.
Conclusion
Today, we learned how to solve the minimum spanning tree problem using Kruskal’s Algorithm. This algorithm has a time complexity of O(E log E), making it efficient relative to the number of edges. I recommend practicing problems like this multiple times as preparation for algorithm problem-solving. I hope it helps you with your coding test preparation in the future!