Java Coding Test Course, Finding Minimum Spanning Tree

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 V and the number of edges E.
The next E lines contain the two vertices and the weight of each edge u, 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

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!