How To Find Minimum Spanning Trees Using Kruskal's Algorithm: A Step-by-Step Guide

In this blog, we'll delve deep into Kruskal's algorithm and see how it works with an example. I'll also provide you with the algorithm and code so let's start.

What's Kruskal's Algorithm

Kruskal's algorithm is a greedy algorithm used to find the minimum spanning tree (MST) of a connected, undirected graph. A minimum spanning tree is a subgraph that includes all the vertices of the original graph with the least possible total edge weight. But before understanding this it's necessary to first understand what a greedy algorithm is.

Greedy algorithm

A greedy algorithm iteratively makes the best local choice at each step to find an overall optimal solution. It follows these steps:

1. Initialization: Start with an empty solution or an initial setup.

2. Selection: Choose the best available option based on a specific criterion, usually the one that appears optimal at the current step.

3. Feasibility Check: Ensure that the selected choice meets the problem's constraints or requirements.

4. Update Solution: Incorporate the selected option into the current solution.

5. Repeat: Continue the process until a complete solution is obtained.

Now that we have understood the Greedy algorithm let's see a step-by-step explanation of Kruskal's algorithm.

Kruskal's algorithm explanation

1. Sort the Edges: Start by sorting all the edges in non-decreasing order based on their weights.

2. Initialize MST: Create an empty set to represent the minimum spanning tree (MST).

3. Select the Smallest Edge: Begin iterating through the sorted edges in ascending order of weights.

4. Check for Cycles: For each edge, check if adding it to the MST creates a cycle. A cycle is formed when the two vertices of the edge are already connected by a path in the MST.

5. Add Edge to MST: If adding the edge does not create a cycle, add it to the MST.

6. Repeat: Continue the process until the MST contains (V-1) edges, where V is the number of vertices in the original graph.

7. Final MST: Once the algorithm is complete, the MST will be formed by the selected edges.

Algorithm

Now, let's understand this algorithm with an example.

Example

Let's take a graph with

Step 1: Sort the edges in non-decreasing order based on their weights.

The sorted edges:

1. (1, 2) with weight 10

2. (4, 3) with weight 20

3. (1, 3) with weight 30

4. (2, 3) with weight 40

5. (1, 4) with weight 50

6. (4, 2) with weight 60

7. (5, 3) with weight 70

8. (5, 4) with weight 80

Step 2: Create an empty set to represent the MST and initialize the disjoint set data structure.

MST = {} Disjoint sets: {1}, {2}, {3}, {4}, {5}

Step 3: Start iterating through the sorted edges.

Step 4: Check if adding the edge creates a cycle and add it to the MST if not.

• Edge (1, 2) with weight 10:

  • Vertices 1 and 2 are in separate sets ({1} and {2}), so we add this edge to the MST.

* MST: {(1, 2)}

• Edge (4, 3) with weight 20:

  • Vertices 4 and 3 are in separate sets ({4} and {3}), so we add this edge to the MST.

* MST: {(1, 2), (4, 3)}

• Edge (1, 3) with weight 30:

  • Vertices 1 and 3 are in different sets ({1} and {3}), so we add this edge to the MST.

* MST: {(1, 2), (4, 3), (1, 3)}

• Edge (2, 3) with weight 40:

  • Vertices 2 and 3 are in the same set ({2} and {3}), adding this edge will create a cycle (1-2-3), so we skip it.

• Edge (1, 4) with weight 50:

  • Vertices 1 and 4 are in the same sets ({1} and {4}), adding this edge will create a cycle (1-3-4), so we skip it.

• Edge (4, 2) with weight 60:

  • Vertices 4 and 2 are in the same sets ({4} and {2}), adding this edge will create a cycle (1-3-4-2), so we skip it.

Step 5: Continue adding edges to the MST until it contains (V-1) edges, where V is the number of vertices (5 in this case).

• Edge (5, 3) with weight 70:

  • Vertices 5 and 3 are in different sets ({5} and {3}), so we add this edge to the MST.

* MST: {(1, 2), (4, 3), (1, 3), (5, 3)}

Step 6: The MST contains (V-1) edges (5-1=4), which completes the algorithm.

Final MST: {(1, 2), (4, 3), (1, 3), (5, 3)}

The final minimum spanning tree includes the edges (1, 2), (4, 3), (1, 3), and (5, 3), with a total weight of 10 + 20 + 30 + 70 = 130.

Hope this example is clear now let's understand its code.

Code📍

import java.util.*;

class Edge implements Comparable<Edge> {
    int src, dest, weight;

    public Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}
public class KruskalAlgorithm {
    // Helper method to find the parent of a node in the disjoint set
    private int findParent(int[] parent, int node) {
        // If the node is not its own parent (i.e., not the root), perform path compression
        if (parent[node] != node) {
            parent[node] = findParent(parent, parent[node]);
        }
        return parent[node];
    }

    // Kruskal's algorithm to find the minimum spanning tree of the graph
    public List<Edge> kruskalMST(List<Edge> edges, int vertices) {
        // Sort the edges in non-decreasing order based on their weights
        edges.sort(Comparator.naturalOrder());

        // List to store the edges of the minimum spanning tree
        List<Edge> minimumSpanningTree = new ArrayList<>();

        // Array to represent the disjoint set data structure
        int[] parent = new int[vertices];
        // Initialize each vertex as its own parent (i.e., each vertex is a separate disjoint set)
        Arrays.setAll(parent, i -> i);

        // Iterate through the sorted edges
        for (Edge edge : edges) {
            // Find the parent (root) of the source vertex of the current edge
            int srcParent = findParent(parent, edge.src);
            // Find the parent (root) of the destination vertex of the current edge
            int destParent = findParent(parent, edge.dest);

            // Check if adding the edge will not create a cycle (source and destination vertices belong to different disjoint sets)
            if (srcParent != destParent) {
                // Add the current edge to the minimum spanning tree
                minimumSpanningTree.add(edge);
                // Merge the disjoint sets containing the source and destination vertices
                // (Make the source vertex's parent point to the destination vertex's parent)
                parent[srcParent] = destParent;
            }
        }

        // Return the minimum spanning tree as a list of edges
        return minimumSpanningTree;
    }
}

Complexity analysis

• Time Complexity: O(E log E) [E is the number of edges]

• Space Complexity: O(E + V) [E is the number of edges, V is the number of vertices]

Kruskal's algorithm's time complexity is primarily dominated by the sorting step, which involves sorting the edges based on their weights. Since E is typically greater than or equal to V in connected graphs, the time complexity is mainly determined by O(E log E). The space complexity is reasonably efficient, requiring space proportional to the number of edges and vertices in the graph.

Now that you have a better understanding of Kruskal's algorithm, it's time to put it into action! Try implementing the algorithm in your favorite programming language and explore its capabilities in solving real-world problems. You can challenge yourself by finding MSTs in different scenarios and graphs, or even contribute to open-source projects that utilize MST algorithms. Happy coding!