Kruskal's Algorithm - Visualization

Graphs

Contents

ProblemExamplesSolutionAlgorithmCode

Problem Statement❯

Given a connected, undirected, weighted graph with V vertices and E edges, the goal is to compute the sum of the edge weights of the Minimum Spanning Tree (MST). The MST is a subset of the edges that connects all vertices together, without any cycles, and with the minimum total edge weight.

Examples❯

Vertices (V) Edges MST Weight Description
4 [(0,1,1), (0,2,3), (1,2,1), (1,3,4), (2,3,2)] 4 Edges chosen: (0-1), (1-2), (2-3)
3 [(0,1,10), (1,2,5), (0,2,15)] 15 Edges chosen: (1-2), (0-1)
5 [(0,1,1), (0,2,7), (1,2,5), (1,3,4), (2,4,6), (3,4,2)] 12 MST edges avoid cycles and select minimal weights
1 [] 0 Single node, no edges
2 [(0,1,100)] 100 Only one edge to connect the two nodes

Solution❯

Understanding the Problem

We are given an undirected, weighted graph. Our goal is to find the Minimum Spanning Tree (MST) — a subset of the edges that connects all vertices with the minimum possible total edge weight, and without forming any cycles.

This means we want to connect all nodes together in the cheapest way possible, avoiding any loops. Among many possible algorithms, Kruskal’s Algorithm is one of the most popular and intuitive methods to solve this.

It works by sorting the edges by weight and picking the smallest ones first — only if they don't form a cycle. To efficiently detect cycles, we use a data structure called Disjoint Set Union (DSU) or Union-Find.

Step-by-Step Solution with Example

Step 1: Understand the Input

Let’s take an example graph:


Vertices: 4
Edges: 
(0 - 1, weight 10)
(0 - 2, weight 6)
(0 - 3, weight 5)
(1 - 3, weight 15)
(2 - 3, weight 4)

Step 2: Sort All Edges by Weight

We sort all edges in non-decreasing order of their weight:


(2 - 3, weight 4)
(0 - 3, weight 5)
(0 - 2, weight 6)
(0 - 1, weight 10)
(1 - 3, weight 15)

Step 3: Initialize Disjoint Sets

Each vertex starts as its own parent in the DSU. No vertices are connected initially. We'll connect them as we pick edges.

Step 4: Process Each Edge

We go through each edge in sorted order:

  • Edge (2 - 3): 2 and 3 are in different sets → include this edge in MST.
  • Edge (0 - 3): 0 and 3 are in different sets → include this edge in MST.
  • Edge (0 - 2): 0 and 2 are in different sets → include this edge in MST.
  • Edge (0 - 1): 0 and 1 are now in the same set → including this would form a cycle → skip.
  • Edge (1 - 3): 1 and 3 are already connected → skip to avoid cycle.

Step 5: Stop When MST Has V - 1 Edges

We stop when we have V - 1 = 3 edges in the MST (since we have 4 vertices).

Final MST Edges:


(2 - 3, weight 4)
(0 - 3, weight 5)
(0 - 2, weight 6)

Total Weight = 4 + 5 + 6 = 15

Edge Cases

  • Disconnected Graph: Kruskal’s Algorithm cannot form a complete MST if the graph is not connected. It will return a spanning forest instead.
  • Multiple Same-Weight Edges: The algorithm still works as long as DSU correctly avoids cycles.
  • Self-loops or Parallel Edges: Self-loops should be ignored. For parallel edges, the one with the smallest weight should be considered.
  • Already a Tree: If the input graph is already a tree, no edge will be skipped, and the result is the original graph itself.

Finally

Kruskal’s Algorithm is a greedy algorithm — it picks the best choice at each step by always selecting the smallest edge. Using the DSU efficiently ensures cycle detection is fast, making Kruskal’s a powerful algorithm for building MSTs — especially for sparse graphs.

By working step by step and thinking about edge selection intuitively, beginners can clearly see how Kruskal’s avoids cycles and builds the MST optimally.

Algorithm Steps❯

  1. Sort all edges of the graph in increasing order of weight.
  2. Initialize a Disjoint Set data structure (Union-Find) for all vertices.
  3. Initialize mst_weight = 0.
  4. Iterate over sorted edges:
    1. For each edge (u, v, w), check if u and v belong to different sets.
    2. If they do, add the edge to the MST and union the sets.
    3. Add the weight w to mst_weight.
  5. Continue until MST includes exactly V - 1 edges.
  6. Return mst_weight as the final result.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

// Disjoint Set Union (Union-Find) implementation
typedef struct {
    int *parent;
    int *rank;
    int size;
} DisjointSet;

DisjointSet *createDisjointSet(int n) {
    DisjointSet *ds = (DisjointSet *)malloc(sizeof(DisjointSet));
    ds->parent = (int *)malloc(n * sizeof(int));
    ds->rank = (int *)calloc(n, sizeof(int));
    ds->size = n;
    for (int i = 0; i < n; i++) {
        ds->parent[i] = i;
    }
    return ds;
}

int findParent(DisjointSet *ds, int u) {
    if (ds->parent[u] != u) {
        ds->parent[u] = findParent(ds, ds->parent[u]);
    }
    return ds->parent[u];
}

int unionSets(DisjointSet *ds, int u, int v) {
    int pu = findParent(ds, u);
    int pv = findParent(ds, v);
    if (pu == pv) return 0;
    if (ds->rank[pu] < ds->rank[pv]) {
        ds->parent[pu] = pv;
    } else if (ds->rank[pu] > ds->rank[pv]) {
        ds->parent[pv] = pu;
    } else {
        ds->parent[pv] = pu;
        ds->rank[pu]++;
    }
    return 1;
}

// Edge structure
typedef struct {
    int u, v, weight;
} Edge;

int compareEdges(const void *a, const void *b) {
    Edge *ea = (Edge *)a;
    Edge *eb = (Edge *)b;
    return ea->weight - eb->weight;
}

int kruskalMST(int V, Edge edges[], int E) {
    qsort(edges, E, sizeof(Edge), compareEdges);
    DisjointSet *ds = createDisjointSet(V);
    int mstWeight = 0;
    int edgeCount = 0;

    for (int i = 0; i < E; i++) {
        if (unionSets(ds, edges[i].u, edges[i].v)) {
            mstWeight += edges[i].weight;
            edgeCount++;
            if (edgeCount == V - 1) break;
        }
    }
    free(ds->parent);
    free(ds->rank);
    free(ds);
    return mstWeight;
}

int main() {
    int V = 4;
    Edge edges[] = {
        {0, 1, 1},
        {0, 2, 3},
        {1, 2, 1},
        {1, 3, 4},
        {2, 3, 2}
    };
    int E = sizeof(edges) / sizeof(edges[0]);
    int result = kruskalMST(V, edges, E);
    printf("MST weight: %d\n", result); // Output: 4
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...