Minimum Spanning Tree Kruskal's Algorithm in DSA Java - Build from Scratch

Minimum Spanning Tree using Kruskal's Algorithm

📖 Scenario: You are working as a network engineer. You need to connect several computers with cables. Each cable has a cost. Your goal is to connect all computers with the least total cost without any loops.

🎯 Goal: Build a program that finds the minimum total cost to connect all computers using Kruskal's algorithm.

📋 What You'll Learn

Create an array of edges with exact weights and nodes

Create a variable to count the number of nodes

Implement Kruskal's algorithm to find the minimum spanning tree

Print the total cost of the minimum spanning tree

💡 Why This Matters

🌍 Real World

Network engineers use minimum spanning trees to design cost-efficient networks connecting computers or devices.

💼 Career

Understanding Kruskal's algorithm helps in roles involving network design, optimization, and graph-based problem solving.

1

Create the graph edges

Create an array of Edge objects called edges with these exact entries: new Edge(0, 1, 4), new Edge(0, 2, 3), new Edge(1, 2, 1), new Edge(1, 3, 2), new Edge(2, 3, 4), new Edge(3, 4, 2), new Edge(4, 5, 6).

DSA Java

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

public class KruskalMST {
    public static void main(String[] args) {
        // Create the edges array here
        // Your code here
    }
}

Hint

Use Edge[] edges = { ... }; with the exact edges listed.

2

Set the number of nodes

Create an integer variable called nodes and set it to 6 to represent the number of computers.

DSA Java

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

public class KruskalMST {
    public static void main(String[] args) {
        Edge[] edges = {
            new Edge(0, 1, 4),
            new Edge(0, 2, 3),
            new Edge(1, 2, 1),
            new Edge(1, 3, 2),
            new Edge(2, 3, 4),
            new Edge(3, 4, 2),
            new Edge(4, 5, 6)
        };
        // Create the nodes variable here
        // Your code here
    }
}

Hint

Use int nodes = 6; to set the number of computers.

3

Implement Kruskal's algorithm

Implement Kruskal's algorithm inside main using the variables edges and nodes. Use a parent array for union-find, sort edges by weight, and select edges that do not form a cycle. Store the sum of selected edges in an integer variable called totalCost.

DSA Java

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

public class KruskalMST {
    public static void main(String[] args) {
        Edge[] edges = {
            new Edge(0, 1, 4),
            new Edge(0, 2, 3),
            new Edge(1, 2, 1),
            new Edge(1, 3, 2),
            new Edge(2, 3, 4),
            new Edge(3, 4, 2),
            new Edge(4, 5, 6)
        };
        int nodes = 6;
        // Implement Kruskal's algorithm here
        // Your code here
    }
}

Hint

Sort edges by weight, use union-find with parent array, and add edge weights to totalCost if they connect different sets.

4

Print the total cost

Print the integer variable totalCost using System.out.println(totalCost); to display the minimum total cost of connecting all computers.

DSA Java

import java.util.Arrays;

class Edge implements Comparable {
    int src, dest, weight;
    Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}

public class KruskalMST {
    static int find(int[] parent, int i) {
        if (parent[i] != i) {
            parent[i] = find(parent, parent[i]);
        }
        return parent[i];
    }

    static void union(int[] parent, int x, int y) {
        int xset = find(parent, x);
        int yset = find(parent, y);
        parent[xset] = yset;
    }

    public static void main(String[] args) {
        Edge[] edges = {
            new Edge(0, 1, 4),
            new Edge(0, 2, 3),
            new Edge(1, 2, 1),
            new Edge(1, 3, 2),
            new Edge(2, 3, 4),
            new Edge(3, 4, 2),
            new Edge(4, 5, 6)
        };
        int nodes = 6;

        Arrays.sort(edges);

        int[] parent = new int[nodes];
        for (int i = 0; i < nodes; i++) {
            parent[i] = i;
        }

        int totalCost = 0;
        for (Edge edge : edges) {
            int x = find(parent, edge.src);
            int y = find(parent, edge.dest);

            if (x != y) {
                totalCost += edge.weight;
                union(parent, x, y);
            }
        }
        // Print the totalCost here
        // Your code here
    }
}

Hint

Use System.out.println(totalCost); to print the final cost.

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