Kruskal’s Algorithm for Minimum Spanning Tree (MST): Explained with Examples

Kruskal’s Algorithm is one of the most efficient methods for finding an MST, especially in sparse graphs where edges are much fewer than vertices. It follows a greedy approach, sorting edges first and building the MST step by step. For dense graphs, where edge-to-vertex ratio is high, Prim’s Algorithm can sometimes be more efficient due to its priority queue-based approach. 

Its relevance has grown with the rise of cloud computing, real-time applications, and large-scale data processing. If you work with graph-based problems, understanding Kruskal’s Algorithm for Minimum Spanning Tree is crucial. This guide breaks down the algorithm with clear steps, examples, and practical applications.

Understanding Kruskal’s Algorithm for Minimum Spanning Tree (MST)

A spanning tree is a subset of a connected graph that links all vertices without cycles. The MST is the spanning tree with the lowest total edge weight, optimizing networks, reducing costs, and improving efficiency in areas like telecommunications, logistics, and system design.

Kruskal’s Algorithm for Minimum Spanning Tree follows a greedy approach. It sorts edges by weight and adds the smallest edge that doesn’t create a cycle. The Union-Find data structure efficiently tracks components, ensuring cycle-free connections. 

This makes Kruskal’s Algorithm particularly useful in domains like telecommunications, where minimizing infrastructure cost is crucial, or in data clustering, where it helps identify the most relevant data groupings based on similarity. 

Key Components of Kruskal’s Algorithm:

• Sorting Edges: Arrange all edges by weight in ascending order.
• Union-Find Data Structure: Tracks connected components and prevents cycles.
• Greedy Edge Selection: Iteratively add the smallest edge that doesn’t form a cycle.
• Cycle Prevention: Uses the find and union operations to check connectivity.
• Graph Connectivity: The algorithm ensures connectivity by adding edges one at a time while preventing cycles, using the Union-Find data structure to track components.

Let’s first compare Kruskal’s Algorithm with Prim’s Algorithm to understand the strengths and weaknesses of each.

How Kruskal’s Algorithm Differs from Prim’s Algorithm

Both Kruskal’s and Prim’s Algorithms solve the MST problem, but they follow different approaches. Kruskal’s Algorithm is edge-based, selecting edges in ascending order, while Prim’s Algorithm is node-based, expanding the tree from a starting vertex. Understanding their differences helps in choosing the right method for a given graph.

The following comparison highlights the key differences between Kruskal’s and Prim’s algorithms:

Understanding Kruskal’s Algorithm in detail helps in determining when it is the most efficient method for finding an MST, especially in sparse graphs. Let’s break down its step-by-step process.

How to Find the Minimum Spanning Tree Using Kruskal’s Algorithm? A Step-by-Step Guide

Kruskal’s Algorithm follows a structured process to build an MST efficiently. It begins by sorting all edges by weight, ensuring that the smallest edges are considered first. The algorithm then iteratively adds edges while using the Union-Find data structure to detect and prevent cycles. 

This approach guarantees that only the minimum-weight edges are included, resulting in an optimal spanning tree.

By following these steps, Kruskal’s Algorithm efficiently constructs an MST, making it ideal for network design, clustering, and large-scale optimization problems. Let’s go through the process in detail.

Step 1: Sort All Edges in Ascending Order of Weight

Sorting ensures the algorithm always picks the smallest available edge first, guaranteeing that the MST has the minimum total weight while maintaining efficiency. Since sorting takes O(E log E) time, it dominates the overall complexity of Kruskal’s Algorithm. 

In comparison, Union-Find operations (with path compression and union by rank) run in nearly O(1) amortized time, adding minimal computational overhead. This balance makes Kruskal’s Algorithm particularly efficient for sparse graphs, where sorting remains manageable.

Start Here:

Extract all edges from the graph and arrange them in ascending order based on their weights using an efficient sorting algorithm.

Process:

1. Collect all edges and their weights.
2. Use an efficient sorting algorithm such as Merge Sort or Quick Sort.
3. Sorting takes O(E log E) time, making it the dominant cost of the algorithm.

Example Input:

Example Result (Sorted Edges):

Also Read: Time Complexity of Kruskal Algorithm: Insights, Comparisons, and Applications

Step 2: Pick the Smallest Edge and Check if it Forms a Cycle

Adding edges in ascending order ensures the MST is built with the least possible weight. However, adding an edge that creates a cycle would violate the spanning tree structure.

Start Here:

Select the smallest edge from the sorted list and check whether it connects two different components.

Process:

1. Pick the smallest edge from the sorted list.
2. Use the Union-Find data structure to check if both vertices belong to different components.
3. If they are in the same component, the edge is skipped to prevent cycles.
4. If they belong to different components, the edge is added to the MST.

Example Execution:

• Edge E–F (2): E and F are not connected, so add it.
• Edge C–D (3): C and D are separate, so add it.
• Edge A–B (4): A and B are separate, so add it.

Also Read: The Shortest Path - Dijkstra Algorithm: A detailed Overview

Step 3: Use Union-Find to Track Components and Avoid Cycles

Tracking which vertices belong to which component helps in determining whether adding an edge will form a cycle. The Union-Find data structure makes this process efficient.

Start Here:

Use the Union-Find data structure to efficiently track components and prevent cycles.

Process:

1. Find operation: Determines which component a node belongs to.

2. Union operation: Merges two components when an edge is added.

3. Path compression: Optimizes Find by linking nodes directly to their root.

4. Union by rank: Ensures smaller trees attach under larger trees, reducing tree height.

Example Execution:

• Edge C–D (3): find(C) ≠ find(D), so union(C, D).
• Edge A–B (4): find(A) ≠ find(B), so union(A, B).
• Edge A–C (6): find(A) ≠ find(C), so union(A, C).
• Edge B–D (7): find(B) = find(D), so this edge is skipped.

Searching in Data Structure: Different Search Algorithms and Their Applications

Step 4: Add the Edge to the MST if No Cycle is Formed

Adding edges without creating cycles ensures that the structure remains a tree while covering all vertices.

Start Here:

Check whether the edge can be added without violating the MST properties.

Process:

1. If two vertices are already in the same component, the edge forms a cycle and must be skipped.
2. If they belong to different components, add the edge to the MST.
3. Keep track of selected edges until the MST contains V-1 edges.

Example Execution:

Final MST edges after filtering out cycles:

Step 5: Repeat Until MST Contains (V-1) Edges

A Minimum Spanning Tree of a graph with V vertices contains exactly V-1 edges to connect all vertices without cycles.

Start Here:

Continue selecting edges until exactly V-1 edges are in the MST.

Process:

1. Count the number of edges in the MST.
2. Stop when the MST reaches V-1 edges, ensuring all vertices are connected.
3. Return the final MST.

Final MST:

Total Weight: 2 + 3 + 4 + 5 + 6 = 20

The MST is now complete.

Edge Cases & Considerations

• What if the graph is already a tree? If the graph is already a tree, Kruskal's Algorithm will not add any additional edges, as it already forms an MST.
• What if the graph is disconnected? Kruskal’s Algorithm finds an MST for each connected component, resulting in a Minimum Spanning Forest.
• What if multiple edges have the same weight? The algorithm may produce multiple valid MSTs, depending on the edge selection order.

Performance Analysis & Optimizations

Why Kruskal’s Algorithm is Efficient

1. Sorting edges first ensures that the smallest edges are processed in order, maintaining a minimum total weight.
2. Union-Find makes cycle detection highly efficient, preventing unnecessary comparisons.
3. Best suited for sparse graphs, where E ≈ V, making it more efficient than Prim’s Algorithm in such cases.

Before applying Kruskal’s Algorithm to real-world problems, let’s walk through some examples to see how it constructs a Minimum Spanning Tree step by step.

Kruskal’s Algorithm in Action: Examples and Applications

Kruskal’s Algorithm is widely used in network design, clustering, and optimization tasks. By breaking down its process in different scenarios, we can understand how it efficiently constructs an MST while avoiding cycles. 

Below, we go through a small graph example to grasp the fundamentals and then apply the algorithm to a larger graph, demonstrating the power of Union-Find for cycle detection and efficiency.

Example 1: Small Graph

Graph Description: Consider a graph with 4 vertices (A, B, C, D) and 5 edges with the following weights:

Step-by-Step Execution

1. Sort edges in ascending order:

• A–B (1), A–C (2), B–C (3), B–D (4), C–D (5).

2. Pick the smallest edge: A–B (1). No cycle, so add to MST.

3. Next edge: A–C (2). No cycle, so add to MST.

4. Next edge: B–C (3). Forms a cycle (A–B–C is already connected), so skip.

5. Next edge: B–D (4). No cycle, so add to MST.

6. Stop when MST has V-1 (3) edges.

Final MST edges: A–B (1), A–C (2), B–D (4)
Total weight: 1 + 2 + 4 = 7

This small example demonstrates Kruskal’s greedy approach—always picking the smallest available edge while preventing cycles.

Example 2: Larger Graph with Union-Find

Graph Description: Consider a graph with 6 vertices and 9 edges:

Step-by-Step Execution with Union-Find

1. Sort edges in ascending order:

• B–C (1), B–D (2), A–C (3), A–B (4), C–D (4), D–E (5), C–E (6), D–F (7), E–F (8).

2. Process edges while ensuring cycle prevention using Union-Find:

• B–C (1): Add to MST.
• B–D (2): Add to MST.
• A–C (3): Add to MST.
• A–B (4): Forms a cycle (A, B, C are already connected), so skip.
• C–D (4): Forms a cycle, so skip.
• D–E (5): Add to MST.
• C–E (6): Forms a cycle, so skip.
• D–F (7): Add to MST.

3. Stop when MST has V-1 (5) edges.

Final MST edges: B–C (1), B–D (2), A–C (3), D–E (5), D–F (7)
Total weight: 1 + 2 + 3 + 5 + 7 = 18

How Union-Find Helps

• Find Operation: Determines if two nodes belong to the same component.
• Union Operation: Merges two components when an edge is added.
• Path Compression: Speeds up Find by flattening the tree.
• Union by Rank: Ensures balanced merging of sets.

By efficiently tracking connected components, Union-Find reduces the complexity of cycle detection, making Kruskal’s Algorithm scalable for larger graphs.

Also Read: What Is Algorithmic Game Theory? Explained With Examples

Kruskal’s Algorithm isn’t just a theoretical concept—it plays a crucial role in solving real-world optimization problems across various industries.

Real-World Applications of Kruskal's Algorithm for Minimum Spanning Tree

Kruskal’s Algorithm is widely applied in solving optimization problems that require minimum-cost connectivity while ensuring efficiency and reliability. Below, we explore its applications across different domains, with real-world example scenarios, techniques used, and why Kruskal’s Algorithm is the best approach in each case.

1. Telecommunication Networks: Optimizing Fiber-Optic Cable Placement

Example Scenario:

A telecom company needs to lay fiber-optic cables between cities to provide high-speed internet. The goal is to connect all cities with the lowest possible infrastructure cost while ensuring redundancy in case of failure.

Methods & Techniques Used:

• Graph Representation: Cities are represented as vertices, and possible cable routes as weighted edges (cost per km).
• Sorting Techniques: Edges (cable routes) are sorted by cost using efficient sorting algorithms like Merge Sort.
• Union-Find for Cycle Detection: Ensures no redundant loops are created in the network.

Why Kruskal’s Algorithm?

• Best suited for sparse networks, where not every city is directly connected.
• Ensures the minimum cost spanning network while avoiding unnecessary cable deployment.
• Can be easily modified to include redundancy by allowing a small number of additional edges.

Real-world example: Google Fiber’s network design and submarine cable routing use similar MST approaches to minimize costs.

2. Transportation Planning: Road and Railway Network Optimization

Example Scenario:

A government agency wants to build a national highway system connecting major cities while minimizing construction costs. They need an optimized network that connects all cities without unnecessary roads.

Methods & Techniques Used:

• Graph Representation: Cities are nodes, possible highways are edges with weights representing construction costs.
• Geographic Data Integration: GIS (Geographic Information System) data is used to analyze road distances and terrain constraints.
• Kruskal’s Algorithm Implementation: Ensures a cost-effective transport network while covering all cities.

Why Kruskal’s Algorithm?

• Ideal for nationwide transport planning, where road networks are not fully interconnected.
• Works efficiently when the number of possible road connections (edges) is much larger than the number of cities (nodes).
• Can be modified for real-world constraints, such as excluding high-terrain routes.

Real-world example: The National Highway Development Program in India used MST-based approaches for road connectivity optimization.

3. Data Clustering in Machine Learning & Hierarchical Clustering

Example Scenario:

A data scientist is developing a customer segmentation model for an e-commerce company. They need to group customers based on purchasing behavior and demographics to target them with personalized ads.

Methods & Techniques Used:

• Graph Representation: Customers are nodes, and similarities (inverse of distance) between them are weighted edges.
• Kruskal’s Algorithm for Hierarchical Clustering: Finds clusters by selecting the most significant relationships between data points.
• Dendrogram Construction: MST helps form clusters in hierarchical clustering techniques.

Why Kruskal’s Algorithm?

• Handles high-dimensional data efficiently by focusing on the strongest connections.
• Works well for agglomerative clustering, where clusters grow by merging the closest data points.
• Avoids redundant connections, making clustering scalable for large datasets.

Real-world example: Amazon’s customer recommendation system uses clustering techniques to group similar buyers based on purchasing behavior.

4. Power Grid and Pipeline Network Optimization

Example Scenario:

An energy company wants to build an electric power distribution network that minimizes transmission loss and reduces cost while ensuring power reaches all cities.

Methods & Techniques Used:

• Graph Representation: Power stations are nodes, transmission lines are weighted edges (cost and energy loss).
• Grid Optimization Algorithms: Kruskal’s MST approach is combined with load balancing techniques.
• Union-Find for Efficient Connection Checking: Ensures every station is connected while avoiding redundant routes.

Why Kruskal’s Algorithm?

• Ideal for nationwide or large-area power distribution, where direct connections between every node aren’t feasible.
• Provides an optimal structure for transmitting electricity with minimal loss.
• Can be extended to include fault-tolerance planning, ensuring backup connections in case of failures.

Real-world example: Power grid design in the U.S. and Europe uses MST-based approaches to optimize transmission routes.

5. Computer Network Design & LAN Setup

Example Scenario:

A university is setting up a Local Area Network (LAN) across multiple buildings with minimal wiring costs.

Methods & Techniques Used:

• Graph Representation: Computers and routers are vertices, potential cable connections are edges with cost as weight.
• Kruskal’s Algorithm for MST Calculation: Determines the optimal way to connect all nodes with minimal cabling.
• Network Redundancy Handling: Extra edges can be added to prevent single points of failure.

Why Kruskal’s Algorithm?

• Best for wired networks where not every device needs to be directly connected.
• Reduces wiring and installation costs while maintaining full connectivity.
• Ensures an efficient data transmission structure within the network.

Real-world example: Corporate LAN and data center interconnections use MST-based network topologies to optimize cost and efficiency.

Why Kruskal’s Algorithm is the Best Choice in These Scenarios?

Kruskal’s Algorithm consistently delivers optimal, cost-effective solutions by ensuring the most efficient connection between points while avoiding unnecessary redundancies. This makes it a powerful tool across industries.

Also Read: Top 25 DBMS Projects [With Source Code] for Students in 2025

Now that we’ve explored the real-world impact of Kruskal’s Algorithm, let’s see how it can be implemented in code.

Code Implementation of Kruskal’s Algorithm for Minimum Spanning Tree

Understanding the logic behind Kruskal’s Algorithm is important, but implementing it in code demonstrates its efficiency in practice. The algorithm follows a structured approach—sorting edges, applying Union-Find, and iterating through the graph to build the MST.

Let’s explore its implementation in multiple programming languages, starting with Python.

Python Implementation of Kruskal’s Algorithm

Kruskal’s Algorithm efficiently finds the Minimum Spanning Tree (MST) using a greedy approach and the Union-Find data structure for cycle detection. Below is a well-commented Python implementation, demonstrating the key steps, including sorting edges, applying Union-Find, and constructing the MST.

Steps in Python Implementation:

• Step 1: Define the Graph with edges and weights.
• Step 2: Sort edges in ascending order of weight.
• Step 3: Implement Union-Find with path compression to track connected components.
• Step 4: Iterate through the sorted edges, adding them to the MST if they don’t form a cycle.
• Step 5: Stop when V-1 edges are added to the MST (where V is the number of vertices).

Python Code Implementation:

class Graph:
    def __init__(self, vertices):
        self.V = vertices  # Number of vertices
        self.edges = []  # Graph edges (u, v, weight)

    def add_edge(self, u, v, w):
        self.edges.append((w, u, v))  # Store edges as (weight, vertex1, vertex2)

    def find(self, parent, i):
        # Find root node using path compression
        if parent[i] != i:
            parent[i] = self.find(parent, parent[i])
        return parent[i]

    def union(self, parent, rank, x, y):
        # Attach smaller rank tree under root of higher rank tree
        root_x = self.find(parent, x)
        root_y = self.find(parent, y)

        if root_x != root_y:
            if rank[root_x] > rank[root_y]:
                parent[root_y] = root_x
            elif rank[root_x] < rank[root_y]:
                parent[root_x] = root_y
            else:
                parent[root_y] = root_x
                rank[root_x] += 1

    def kruskal_mst(self):
        # Step 1: Sort edges by weight
        self.edges.sort()

        parent = []
        rank = []
        mst = []

        # Step 2: Initialize Union-Find structure
        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        # Step 3: Pick the smallest edge and check for cycles
        for edge in self.edges:
            w, u, v = edge
            root_u = self.find(parent, u)
            root_v = self.find(parent, v)

            # Step 4: If u and v are in different sets, add to MST
            if root_u != root_v:
                mst.append((u, v, w))
                self.union(parent, rank, root_u, root_v)

            # Step 5: Stop when we have V-1 edges in MST
            if len(mst) == self.V - 1:
                break

        # Step 6: Print the MST
        print("Edges in the Minimum Spanning Tree:")
        for u, v, weight in mst:
            print(f"{u} -- {v} == {weight}")
        return mst

# Example Usage:
g = Graph(6)
g.add_edge(0, 1, 4)
g.add_edge(0, 2, 3)
g.add_edge(1, 2, 1)
g.add_edge(1, 3, 2)
g.add_edge(2, 3, 4)
g.add_edge(3, 4, 2)
g.add_edge(4, 5, 6)
g.add_edge(3, 5, 3)

mst = g.kruskal_mst()

Explanation of Output:

For the given graph with 6 vertices and 8 edges, the algorithm follows these steps:

1. Sort the edges by weight

• (1,2) → 1
• (1,3) → 2
• (3,4) → 2
• (0,2) → 3
• (3,5) → 3
• (0,1) → 4
• (2,3) → 4
• (4,5) → 6

2. Iterate and build the MST

• Pick (1,2), (1,3), (3,4), (0,2), and (3,5) as they do not form a cycle.
• Stop when 5 edges are added (since V-1 = 5).

3. Final MST Output:

Edges in the Minimum Spanning Tree:
1 -- 2 == 1
1 -- 3 == 2
3 -- 4 == 2
0 -- 2 == 3
3 -- 5 == 3

Total MST Weight: 1 + 2 + 2 + 3 + 3 = 11

Why Union-Find with Path Compression is Used?

• Find with path compression: Flattens the tree structure, making subsequent lookups almost O(1).
• Union by rank: Ensures smaller trees attach under larger ones, keeping operations efficient.
• Overall Efficiency: O(E log E) due to sorting, followed by near O(1) Union-Find operations.

Why Kruskal’s Algorithm Works Well in Python?

• Python’s built-in sorting (Timsort, O(E log E)) efficiently handles large graphs with sorted() or heapq for priority-based processing.
• Dictionary-based Union-Find (using dict and defaultdict) optimizes performance for dynamic graph operations.
• List comprehensions and set operations speed up graph traversal and edge filtering.
• Used in real-world applications like network routing, where Python’s networkx library helps visualize and optimize MST-based structures.

New to coding? Learn Basic Python Programming with upGrad in just 12 hours and build the foundation to implement Kruskal’s Algorithm for MST efficiently.

C Implementation of Kruskal’s Algorithm

Kruskal’s Algorithm can be efficiently implemented in C using structs and arrays for representing edges and the Union-Find data structure for cycle detection. Below, we provide a well-structured C implementation that sorts edges, applies Union-Find with path compression, and constructs the MST step by step.

 Key Steps in C Implementation:

• Step 1: Define a Graph structure with vertices and edges.
• Step 2: Sort edges using Quick Sort or Merge Sort for efficiency.
• Step 3: Implement Union-Find with path compression to track connected components.
• Step 4: Iterate through the sorted edges, adding them to the MST if they don’t form a cycle.
• Step 5: Stop when V-1 edges are added to the MST.

C Code Implementation:

#include <stdio.h>
#include <stdlib.h>

// Structure to represent an edge
typedef struct {
    int src, dest, weight;
} Edge;

// Structure to represent a graph
typedef struct {
    int V, E;
    Edge* edges;
} Graph;

// Function to create a graph
Graph* createGraph(int V, int E) {
    Graph* graph = (Graph*) malloc(sizeof(Graph));
    graph->V = V;
    graph->E = E;
    graph->edges = (Edge*) malloc(E * sizeof(Edge));
    return graph;
}

// Function to compare edges by weight for sorting
int compareEdges(const void* a, const void* b) {
    return ((Edge*)a)->weight - ((Edge*)b)->weight;
}

// Union-Find: Find function with path compression
int find(int parent[], int i) {
    if (parent[i] != i)
        parent[i] = find(parent, parent[i]);
    return parent[i];
}

// Union-Find: Union function with rank optimization
void unionSets(int parent[], int rank[], int x, int y) {
    int rootX = find(parent, x);
    int rootY = find(parent, y);

    if (rootX != rootY) {
        if (rank[rootX] > rank[rootY])
            parent[rootY] = rootX;
        else if (rank[rootX] < rank[rootY])
            parent[rootX] = rootY;
        else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

// Function to implement Kruskal's algorithm
void kruskalMST(Graph* graph) {
    int V = graph->V;
    Edge result[V - 1];  // Store the MST edges
    int e = 0, i = 0;  // Index for result and edges

    // Step 1: Sort edges by weight
    qsort(graph->edges, graph->E, sizeof(graph->edges[0]), compareEdges);

    // Step 2: Initialize Union-Find structure
    int parent[V], rank[V];
    for (int v = 0; v < V; v++) {
        parent[v] = v;
        rank[v] = 0;
    }

    // Step 3: Iterate through sorted edges
    while (e < V - 1 && i < graph->E) {
        Edge nextEdge = graph->edges[i++];
        int x = find(parent, nextEdge.src);
        int y = find(parent, nextEdge.dest);

        // If adding this edge does not create a cycle, include it in MST
        if (x != y) {
            result[e++] = nextEdge;
            unionSets(parent, rank, x, y);
        }
    }

    // Step 4: Print the MST
    printf("Edges in the Minimum Spanning Tree:\n");
    for (i = 0; i < e; i++)
        printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);
}

// Main function to test Kruskal's Algorithm
int main() {
    int V = 6, E = 8;
    Graph* graph = createGraph(V, E);

    graph->edges[0] = (Edge){0, 1, 4};
    graph->edges[1] = (Edge){0, 2, 3};
    graph->edges[2] = (Edge){1, 2, 1};
    graph->edges[3] = (Edge){1, 3, 2};
    graph->edges[4] = (Edge){2, 3, 4};
    graph->edges[5] = (Edge){3, 4, 2};
    graph->edges[6] = (Edge){4, 5, 6};
    graph->edges[7] = (Edge){3, 5, 3};

    kruskalMST(graph);
    free(graph->edges);
    free(graph);

    return 0;
}

Explanation of Output:

For the given graph with 6 vertices and 8 edges, the algorithm follows these steps:

1. Sort edges by weight

• (1,2) → 1
• (1,3) → 2
• (3,4) → 2
• (0,2) → 3
• (3,5) → 3
• (0,1) → 4
• (2,3) → 4
• (4,5) → 6

2. Iterate and build the MST

• Pick (1,2), (1,3), (3,4), (0,2), and (3,5) as they do not form a cycle.
• Stop when 5 edges are added (since V-1 = 5).

3. Final MST Output:

Edges in the Minimum Spanning Tree:
1 -- 2 == 1
1 -- 3 == 2
3 -- 4 == 2
0 -- 2 == 3
3 -- 5 == 3

Total MST Weight: 1 + 2 + 2 + 3 + 3 = 11

Sorting Efficiency: Quick Sort vs. Merge Sort

• Quick Sort:
  • Average case: O(E log E)
  • Worst case: O(E²) (if pivot is poorly chosen)
  • Faster in practice for small and medium graphs.
• Merge Sort:
  • Guaranteed O(E log E) complexity.
  • Stable sorting (preserves order of equal elements).
  • Better for very large datasets.

Since Kruskal’s Algorithm is dominated by the sorting step, choosing the right sorting algorithm impacts overall performance.

5. Why Use Union-Find with Path Compression?

• Find with path compression:
  • Reduces lookup time by flattening the tree structure.
  • Ensures near O(1) amortized time complexity for Find operations.
• Union by rank:
  • Keeps tree height small, making Union operations faster.
  • Improves efficiency in dense graphs.
• Overall Complexity:
  • O(E log E) due to sorting, followed by O(1) Union-Find operations.

Why Kruskal’s Algorithm Works Well in C?

• Efficient memory usage with struct-based representation.
• Quick sorting algorithms improve performance.
• Direct memory access ensures fast Union-Find operations.
• Ideal for embedded systems, network routing, and large-scale optimizations.

C++ Implementation of Kruskal’s Algorithm

Kruskal’s Algorithm can be efficiently implemented in C++ using the Disjoint Set (Union-Find) data structure for cycle detection and std::sort for edge sorting. Below, we provide a C++ implementation that demonstrates the use of path compression for quick cycle detection and efficient MST construction.

 Key Steps in C++ Implementation:

• Step 1: Define a Graph structure using vectors and structs to store edges.
• Step 2: Use std::sort to efficiently sort edges in O(E log E) time.
• Step 3: Implement Union-Find with path compression for cycle detection.
• Step 4: Iterate through the sorted edges, adding them to the MST if they don’t form a cycle.
• Step 5: Stop when V-1 edges are added to the MST.

C++ Code Implementation:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Structure to represent an edge
struct Edge {
    int src, dest, weight;
};

// Structure to represent a graph
class Graph {
public:
    int V, E;
    vector<Edge> edges;

    Graph(int V, int E) {
        this->V = V;
        this->E = E;
    }

    void addEdge(int u, int v, int w) {
        edges.push_back({u, v, w});
    }
};

// Disjoint Set (Union-Find) class
class DisjointSet {
    vector<int> parent, rank;

public:
    DisjointSet(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    // Find with path compression
    int find(int u) {
        if (parent[u] != u)
            parent[u] = find(parent[u]);
        return parent[u];
    }

    // Union by rank
    void unite(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU != rootV) {
            if (rank[rootU] > rank[rootV])
                parent[rootV] = rootU;
            else if (rank[rootU] < rank[rootV])
                parent[rootU] = rootV;
            else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
        }
    }
};

// Kruskal's Algorithm function
void kruskalMST(Graph& graph) {
    vector<Edge> mst;
    int mst_weight = 0;

    // Step 1: Sort edges by weight using std::sort
    sort(graph.edges.begin(), graph.edges.end(), [](Edge a, Edge b) {
        return a.weight < b.weight;
    });

    // Step 2: Initialize Disjoint Set
    DisjointSet ds(graph.V);

    // Step 3: Process edges and add to MST if no cycle is formed
    for (auto edge : graph.edges) {
        if (ds.find(edge.src) != ds.find(edge.dest)) {
            mst.push_back(edge);
            mst_weight += edge.weight;
            ds.unite(edge.src, edge.dest);
        }

        // Step 4: Stop when MST has V-1 edges
        if (mst.size() == graph.V - 1)
            break;
    }

    // Step 5: Print MST
    cout << "Edges in the Minimum Spanning Tree:\n";
    for (auto edge : mst)
        cout << edge.src << " -- " << edge.dest << " == " << edge.weight << endl;
    cout << "Total MST Weight: " << mst_weight << endl;
}

// Main function
int main() {
    int V = 6, E = 8;
    Graph graph(V, E);

    graph.addEdge(0, 1, 4);
    graph.addEdge(0, 2, 3);
    graph.addEdge(1, 2, 1);
    graph.addEdge(1, 3, 2);
    graph.addEdge(2, 3, 4);
    graph.addEdge(3, 4, 2);
    graph.addEdge(4, 5, 6);
    graph.addEdge(3, 5, 3);

    kruskalMST(graph);

    return 0;
}

Explanation of Output:

For the given graph with 6 vertices and 8 edges, the algorithm follows these steps:

1. Sort edges by weight

• (1,2) → 1
• (1,3) → 2
• (3,4) → 2
• (0,2) → 3
• (3,5) → 3
• (0,1) → 4
• (2,3) → 4
• (4,5) → 6

2. Iterate and build the MST

• Pick (1,2), (1,3), (3,4), (0,2), and (3,5) as they do not form a cycle.
• Stop when 5 edges are added (since V-1 = 5).

3. Final MST Output:

Edges in the Minimum Spanning Tree:
1 -- 2 == 1
1 -- 3 == 2
3 -- 4 == 2
0 -- 2 == 3
3 -- 5 == 3
Total MST Weight: 11

Total MST Weight: 1 + 2 + 2 + 3 + 3 = 11

Sorting Efficiency: std::sort in C++

• std::sort uses Introsort (Hybrid of Quick Sort, Heap Sort, and Insertion Sort).
• Time Complexity: O(E log E) in worst-case scenarios.
• Efficient for large datasets, since it optimizes based on input size.

Since sorting dominates Kruskal’s Algorithm, std::sort significantly improves performance compared to traditional sorting methods.

Why Use Union-Find with Path Compression?

• Find with path compression:
  • Reduces lookup time by flattening the tree structure.
  • Ensures near O(1) amortized time complexity for Find operations.
• Union by rank:
  • Keeps tree height small, making Union operations faster.
  • Improves efficiency in dense graphs.
• Overall Complexity:
  • O(E log E) due to sorting, followed by O(1) Union-Find operations.

Why Kruskal’s Algorithm Works Well in C++?

• Efficient STL (Standard Template Library) support with vector and std::sort.
• Faster execution compared to other languages due to low-level memory management.
• Disjoint Set (Union-Find) in O(1) using path compression.
• Ideal for large-scale applications in networking, clustering, and graph processing.

Java Implementation of Kruskal’s Algorithm Using Union-Find

Kruskal’s Algorithm can be efficiently implemented in Java using a priority queue (PriorityQueue) or Collections.sort() for sorting edges and the Union-Find (Disjoint Set) data structure for cycle detection. 

Below, we provide a Java implementation that demonstrates the use of path compression for quick cycle detection and rank optimization for efficient merging of sets.

Key Steps in Java Implementation:

• Step 1: Define a Graph structure using classes for edges and the disjoint set.
• Step 2: Use Collections.sort() or PriorityQueue to efficiently sort edges in O(E log E) time.
• Step 3: Implement Union-Find with path compression to track connected components.
• Step 4: Iterate through the sorted edges, adding them to the MST if they don’t form a cycle.
• Step 5: Stop when V-1 edges are added to the MST.

Java Code Implementation:

import java.util.*;

// Class to represent an edge in a graph
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;
    }
}

// Disjoint Set (Union-Find) class
class DisjointSet {
    int[] parent, rank;

    public DisjointSet(int n) {
        parent = new int[n];
        rank = new int[n];

        // Initialize each node as its own parent
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    // Find with path compression
    public int find(int u) {
        if (parent[u] != u)
            parent[u] = find(parent[u]);
        return parent[u];
    }

    // Union by rank
    public void union(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);

        if (rootU != rootV) {
            if (rank[rootU] > rank[rootV])
                parent[rootV] = rootU;
            else if (rank[rootU] < rank[rootV])
                parent[rootU] = rootV;
            else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
        }
    }
}

// Graph class to store edges and implement Kruskal's Algorithm
class Graph {
    int V, E;
    List<Edge> edges = new ArrayList<>();

    public Graph(int V, int E) {
        this.V = V;
        this.E = E;
    }

    public void addEdge(int src, int dest, int weight) {
        edges.add(new Edge(src, dest, weight));
    }

    public void kruskalMST() {
        List<Edge> mst = new ArrayList<>();
        int mstWeight = 0;

        // Step 1: Sort edges by weight using Collections.sort()
        Collections.sort(edges);

        // Step 2: Initialize Union-Find structure
        DisjointSet ds = new DisjointSet(V);

        // Step 3: Process edges and add to MST if no cycle is formed
        for (Edge edge : edges) {
            if (ds.find(edge.src) != ds.find(edge.dest)) {
                mst.add(edge);
                mstWeight += edge.weight;
                ds.union(edge.src, edge.dest);
            }

            // Step 4: Stop when MST has V-1 edges
            if (mst.size() == V - 1)
                break;
        }

        // Step 5: Print MST
        System.out.println("Edges in the Minimum Spanning Tree:");
        for (Edge edge : mst)
            System.out.println(edge.src + " -- " + edge.dest + " == " + edge.weight);
        System.out.println("Total MST Weight: " + mstWeight);
    }
}

// Main function
public class KruskalAlgorithm {
    public static void main(String[] args) {
        int V = 6, E = 8;
        Graph graph = new Graph(V, E);

        graph.addEdge(0, 1, 4);
        graph.addEdge(0, 2, 3);
        graph.addEdge(1, 2, 1);
        graph.addEdge(1, 3, 2);
        graph.addEdge(2, 3, 4);
        graph.addEdge(3, 4, 2);
        graph.addEdge(4, 5, 6);
        graph.addEdge(3, 5, 3);

        graph.kruskalMST();
    }
}

Explanation of Output:

For the given graph with 6 vertices and 8 edges, the algorithm follows these steps:

1. Sort edges by weight

• (1,2) → 1
• (1,3) → 2
• (3,4) → 2
• (0,2) → 3
• (3,5) → 3
• (0,1) → 4
• (2,3) → 4
• (4,5) → 6

2. Iterate and build the MST

• Pick (1,2), (1,3), (3,4), (0,2), and (3,5) as they do not form a cycle.
• Stop when 5 edges are added (since V-1 = 5).

3. Final MST Output:

Edges in the Minimum Spanning Tree:
1 -- 2 == 1
1 -- 3 == 2
3 -- 4 == 2
0 -- 2 == 3
3 -- 5 == 3
Total MST Weight: 11

Sorting Efficiency: Collections.sort() vs. PriorityQueue

• Collections.sort()
  • Uses Timsort (Hybrid of Merge Sort and Insertion Sort).
  • O(E log E) worst-case complexity.
  • Best when sorting once before processing edges.
• PriorityQueue
  • Implements a Min-Heap, ensuring that edges are processed in increasing order.
  • Insertion/removal operations take O(log E) each.
  • Best when edges arrive dynamically in real-world scenarios.

Since sorting dominates Kruskal’s Algorithm, Collections.sort() or PriorityQueue significantly improve performance.

Why Use Union-Find with Path Compression?

• Find with path compression:
  • Reduces lookup time by flattening the tree structure.
  • Ensures near O(1) amortized time complexity for Find operations.
• Union by rank:
  • Keeps tree height small, making Union operations faster.
  • Improves efficiency in dense graphs.
• Overall Complexity:
  • O(E log E) due to sorting, followed by O(1) Union-Find operations.

 Why Kruskal’s Algorithm Works Well in Java?

• Efficient sorting via Collections.sort() and PriorityQueue.
• Robust memory management with objects and lists.
• Union-Find in O(1) using path compression.
• Ideal for large-scale applications in networking, clustering, and graph processing.

Also Read: Top 9 Data Science Algorithms Every Data Scientist Should Know

Learn Core Java Basics by upGrad in just 23 hours, covering IntelliJ, data strategy, and coding essentials. Build the skills to implement Kruskal’s Algorithm for MST efficiently.

How Can upGrad Help You Master Kruskal’s Algorithm?

Professionals across industries rely on efficient algorithms like Kruskal’s Algorithm to optimize network design, clustering, and data connectivity. upGrad’s industry-focused programs provide in-depth training in graph theory, algorithmic problem-solving, and large-scale data processing, helping you build real-world expertise.

With a global network of 10 million+ learners, 200+ courses, and 1,400+ hiring partners, upGrad ensures career growth through hands-on learning and industry collaboration.

Here are some of upGrad’s master’s courses to help you gain industry-ready expertise in big data integration, analytics, and dashboarding:

• Master’s Degree in Artificial Intelligence and Data Science
• Masters in Data Science Degree
• Post Graduate Certificate in Data Science & AI (Executive)

upGrad also offers specialized diplomas and certification programs for rapid upskilling in data analytics, visualization techniques, and AI-powered insights:

• Executive Diploma in Data Science & AI with IIIT-B
• Professional Certificate Program in AI and Data Science

Wondering how to apply graph algorithms and MST concepts to real-world challenges? Get personalized career counseling to identify the best opportunities for you. Visit upGrad’s offline centers for expert mentorship, hands-on workshops, and networking sessions to connect you with industry leaders!

Expand your expertise with the best resources available. Browse the programs below to find your ideal fit in Best Machine Learning and AI Courses Online.

Best Machine Learning and AI Courses Online

Discover in-demand Machine Learning skills to expand your expertise. Explore the programs below to find the perfect fit for your goals.

In-demand Machine Learning Skills

Discover popular AI and ML blogs and free courses to deepen your expertise. Explore the programs below to find your perfect fit.

Popular AI and ML Blogs & Free Courses