Minimum Spanning Tree Kruskal's Algorithm in DSA Java

Mental Model

Pick the smallest edges one by one without making loops until all points connect.

Analogy: Imagine building roads between cities by always choosing the cheapest road that doesn't create a circle, so all cities connect with minimum cost.

Graph:
  (1)---2---(2)
   |         |
   3         1
   |         |
  (3)---4---(4)

Edges sorted by weight:
[ (2-4,1), (1-2,2), (1-3,3), (3-4,4) ]

Dry Run Walkthrough

Input: Graph with 4 nodes and edges: (1-2,2), (1-3,3), (2-4,1), (3-4,4)

Goal: Build a tree connecting all nodes with minimum total edge weight without cycles

Step 1: Pick edge (2-4) with weight 1

Edges chosen: (2-4,1)
Sets: {1}, {2,4}, {3}

Why: Start with the smallest edge to connect nodes 2 and 4

Step 2: Pick edge (1-2) with weight 2

Edges chosen: (2-4,1), (1-2,2)
Sets: {1,2,4}, {3}

Why: Add next smallest edge connecting node 1 to the existing set without cycle

Step 3: Pick edge (1-3) with weight 3

Edges chosen: (2-4,1), (1-2,2), (1-3,3)
Sets: {1,2,3,4}

Why: Add edge connecting node 3 to the set, completing the spanning tree

Step 4: Skip edge (3-4) with weight 4 because it creates a cycle

Edges chosen: (2-4,1), (1-2,2), (1-3,3)
Sets: {1,2,3,4}

Why: Adding this edge would create a loop, so we skip it

Result:

Edges chosen: (2-4,1) -> (1-2,2) -> (1-3,3)
All nodes connected with minimum total weight 6

Annotated Code

DSA Java

import java.util.*;

class Edge implements Comparable<Edge> {
    int src, dest, weight;
    Edge(int s, int d, int w) {
        src = s; dest = d; weight = w;
    }
    public int compareTo(Edge other) {
        return this.weight - other.weight; // sort edges by weight ascending
    }
}

class DisjointSet {
    int[] parent, rank;
    DisjointSet(int n) {
        parent = new int[n+1];
        rank = new int[n+1];
        for (int i = 1; i <= n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // path compression
        return parent[x];
    }
    boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return false; // cycle detected
        if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
        else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
        else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }
}

public class KruskalMST {
    public static List<Edge> kruskal(int n, List<Edge> edges) {
        Collections.sort(edges); // sort edges by weight
        DisjointSet ds = new DisjointSet(n);
        List<Edge> mst = new ArrayList<>();
        for (Edge e : edges) {
            if (ds.union(e.src, e.dest)) {
                mst.add(e); // add edge if it doesn't create cycle
            }
        }
        return mst;
    }

    public static void main(String[] args) {
        int n = 4;
        List<Edge> edges = Arrays.asList(
            new Edge(1, 2, 2),
            new Edge(1, 3, 3),
            new Edge(2, 4, 1),
            new Edge(3, 4, 4)
        );
        List<Edge> mst = kruskal(n, edges);
        int totalWeight = 0;
        for (Edge e : mst) {
            System.out.println("Edge: " + e.src + " - " + e.dest + " weight: " + e.weight);
            totalWeight += e.weight;
        }
        System.out.println("Total weight: " + totalWeight);
    }
}

Collections.sort(edges); // sort edges by weight

sort edges ascending by weight to pick smallest first

if (ds.union(e.src, e.dest)) {

add edge only if it connects two different sets (no cycle)

if (parent[x] != x) parent[x] = find(parent[x]); // path compression

find root parent with path compression to speed up future finds

if (rootX == rootY) return false; // cycle detected

detect cycle if both nodes share same root

parent[rootY] = rootX; rank[rootX]++;

union by rank to keep tree shallow

Output

Edge: 2 - 4 weight: 1

Edge: 1 - 2 weight: 2

Edge: 1 - 3 weight: 3

Total weight: 6

Complexity Analysis

Time: O(E log E) because sorting edges dominates and union-find operations are almost O(1)

Space: O(V + E) for storing edges and disjoint set arrays

vs Alternative: Compared to Prim's algorithm which uses priority queues and adjacency lists, Kruskal is simpler for sparse graphs but sorting edges can be costly for dense graphs

Edge Cases

Empty graph with no edges

Returns empty MST with no edges

DSA Java

for (Edge e : edges) { if (ds.union(e.src, e.dest)) {

Graph with single node

Returns empty MST as no edges exist

DSA Java

for (Edge e : edges) { if (ds.union(e.src, e.dest)) {

Graph with multiple edges having same weight

Algorithm picks edges in sorted order and union-find prevents cycles correctly

DSA Java

if (ds.union(e.src, e.dest)) {

When to Use This Pattern

When you need to connect all points with minimum total cost and avoid cycles, reach for Kruskal's MST using edge sorting and union-find to efficiently build the tree.

Common Mistakes

Mistake: Not sorting edges before processing
Fix: Sort edges by weight ascending before starting union-find

Mistake: Not using union-find or cycle detection, causing loops in MST
Fix: Use union-find to check if adding edge creates cycle and skip if it does

Summary

Builds a minimum cost tree connecting all nodes without cycles by picking smallest edges first.

Use when you want the cheapest way to connect all points in a network.

Sort edges by weight and use union-find to avoid cycles while adding edges.

Practice

1. What is the main goal of Kruskal's algorithm in graph theory?

easy

A. To detect cycles in a graph

B. To find the shortest path between two nodes

C. To find the minimum spanning tree of a graph

D. To sort the vertices of a graph

Solution

1. Step 1: Understand Kruskal's algorithm purpose

   Kruskal's algorithm is designed to find a subset of edges that connects all vertices with the minimum total edge weight and no cycles.

2. Step 2: Compare with other graph problems

   Shortest path and cycle detection are different problems solved by other algorithms like Dijkstra or DFS.

3. Final Answer:

   To find the minimum spanning tree of a graph -> Option C

4. Quick Check:

   Minimum Spanning Tree = Find minimum edges connecting all nodes [OK]

Hint: Kruskal always builds minimum spanning tree by edges [OK]

Common Mistakes:

• Confusing MST with shortest path
• Thinking Kruskal detects cycles only
• Assuming it sorts vertices

2. Which Java data structure is commonly used to efficiently check and union sets in Kruskal's algorithm?

easy

A. Disjoint Set (Union-Find)

B. PriorityQueue

C. ArrayList

D. HashMap

Solution

1. Step 1: Identify the need for set operations

   Kruskal's algorithm requires checking if two vertices belong to the same set and merging sets without cycles.

2. Step 2: Match data structure to operations

   Disjoint Set (Union-Find) supports fast union and find operations, ideal for this purpose.

3. Final Answer:

   Disjoint Set (Union-Find) -> Option A

4. Quick Check:

   Union-Find = fast set checks and merges [OK]

Hint: Use Union-Find to detect cycles fast in Kruskal [OK]

Common Mistakes:

• Using ArrayList for set operations
• Confusing PriorityQueue with Union-Find
• Using HashMap which is not efficient here

3. What is the output MST edges after running Kruskal's algorithm on this graph?

Vertices: 1, 2, 3, 4
Edges with weights:
1-2: 1
1-3: 3
2-3: 2
3-4: 4
2-4: 5

medium

A. [1-2, 2-3, 3-4]

B. [1-3, 2-3, 3-4]

C. [1-2, 1-3, 2-4]

D. [1-2, 2-4, 3-4]

Solution

1. Step 1: Sort edges by weight

   Edges sorted: 1-2(1), 2-3(2), 1-3(3), 3-4(4), 2-4(5)

2. Step 2: Pick edges without cycles

   Pick 1-2, then 2-3 (no cycle), then 1-3 creates cycle so skip, pick 3-4 (no cycle), skip 2-4 (cycle)

3. Final Answer:

   [1-2, 2-3, 3-4] -> Option A

4. Quick Check:

   Edges chosen by increasing weight without cycles [OK]

Hint: Sort edges by weight, pick smallest without cycle [OK]

Common Mistakes:

• Picking edges that form cycles
• Not sorting edges by weight
• Choosing heavier edges first

4. Identify the error in this Java snippet for Kruskal's algorithm:

for (Edge e : edges) {
  if (findSet(e.u) != findSet(e.v)) {
    union(e.u, e.v);
    mst.add(e);
  }
}
Collections.sort(edges);

medium

A. Union should be called before findSet

B. Edges should be sorted before the loop

C. mst.add(e) should be outside the if condition

D. The loop should iterate over mst, not edges

Solution

1. Step 1: Check order of sorting and iteration

   Kruskal's requires edges sorted by weight before processing to pick smallest edges first.

2. Step 2: Identify mistake in code order

   Sorting is done after the loop, so edges are not processed in correct order.

3. Final Answer:

   Edges should be sorted before the loop -> Option B

4. Quick Check:

   Sort edges first, then pick edges [OK]

Hint: Sort edges before loop to pick smallest first [OK]

Common Mistakes:

• Sorting edges after processing
• Calling union before checking sets
• Adding edges outside condition

5. Given a graph with edges:

Edges: (A-B, 4), (A-C, 3), (B-C, 2), (B-D, 5), (C-D, 7), (C-E, 8), (D-E, 6)

Using Kruskal's algorithm, what is the total weight of the minimum spanning tree?

hard

A. 18

B. 14

C. 20

D. 16

Solution

1. Step 1: Sort edges by weight

   Sorted edges: B-C(2), A-C(3), A-B(4), B-D(5), D-E(6), C-D(7), C-E(8)

2. Step 2: Pick edges without cycles until all vertices connected

   Pick B-C(2), A-C(3), A-B(4) forms cycle so skip, pick B-D(5), pick D-E(6). Total edges chosen: B-C, A-C, B-D, D-E.

3. Step 3: Calculate total weight

   2 + 3 + 5 + 6 = 16. But A-B(4) skipped due to cycle, so MST edges are B-C, A-C, B-D, D-E.

4. Step 4: Re-check cycle with A-B(4)

   Actually, A-B(4) creates cycle with A-C and B-C, so skip it. MST weight is 2+3+5+6=16.

5. Final Answer:

   16 -> Option D

6. Quick Check:

   Sum of chosen edges weights = 16 [OK]

Hint: Sort edges, pick smallest without cycle, sum weights [OK]

Common Mistakes:

• Including edges that form cycles
• Misordering edges by weight
• Adding all edges without checking cycles