Minimum Spanning Tree Kruskal's Algorithm in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kruskal's MST edges

What is the output of the following Java code that runs Kruskal's algorithm on a graph with 4 vertices and edges with weights?

DSA Java

import java.util.*;

class Edge implements Comparable<Edge> {
    int src, dest, weight;
    public Edge(int s, int d, int w) {
        src = s; dest = d; weight = w;
    }
    public int compareTo(Edge e) {
        return this.weight - e.weight;
    }
}

class Graph {
    int V;
    List<Edge> edges;
    public Graph(int v) {
        V = v;
        edges = new ArrayList<>();
    }
    void addEdge(int s, int d, int w) {
        edges.add(new Edge(s, d, w));
    }
    int find(int[] parent, int i) {
        if (parent[i] == i) return i;
        return find(parent, parent[i]);
    }
    void union(int[] parent, int[] rank, int x, int y) {
        int xroot = find(parent, x);
        int yroot = find(parent, y);
        if (rank[xroot] < rank[yroot]) parent[xroot] = yroot;
        else if (rank[yroot] < rank[xroot]) parent[yroot] = xroot;
        else {
            parent[yroot] = xroot;
            rank[xroot]++;
        }
    }
    List<Edge> kruskalMST() {
        Collections.sort(edges);
        int[] parent = new int[V];
        int[] rank = new int[V];
        for (int i = 0; i < V; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
        List<Edge> result = new ArrayList<>();
        for (Edge e : edges) {
            int x = find(parent, e.src);
            int y = find(parent, e.dest);
            if (x != y) {
                result.add(e);
                union(parent, rank, x, y);
            }
        }
        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph(4);
        g.addEdge(0, 1, 10);
        g.addEdge(0, 2, 6);
        g.addEdge(0, 3, 5);
        g.addEdge(1, 3, 15);
        g.addEdge(2, 3, 4);
        List<Edge> mst = g.kruskalMST();
        for (Edge e : mst) {
            System.out.print("(" + e.src + "," + e.dest + ") ");
        }
    }
}

A (0,2) (0,3) (1,3)

B (0,3) (2,3) (1,3)

C (2,3) (0,3) (0,1)

D (0,1) (1,3) (2,3)

💡 Hint

Remember Kruskal's algorithm picks edges in increasing order of weight without forming cycles.

The edges sorted by weight are (2,3)=4, (0,3)=5, (0,2)=6, (0,1)=10, (1,3)=15. The MST picks (2,3), (0,3), and (0,1) to connect all vertices without cycles.

🧠 Conceptual

intermediate

Understanding cycle detection in Kruskal's algorithm

In Kruskal's algorithm, what is the main purpose of the 'union-find' data structure?

A To keep track of which vertices are connected to avoid cycles

B To store the weights of edges for sorting

C To count the total number of edges in the graph

D To find the shortest path between two vertices

💡 Hint

Think about how Kruskal avoids adding edges that form loops.

Union-find helps quickly check if two vertices belong to the same connected component, preventing cycles when adding edges.

🔧 Debug

advanced

Identify the error in this Kruskal's implementation snippet

What error will the following Java code snippet cause when running Kruskal's algorithm?

DSA Java

int find(int[] parent, int i) {
    while (parent[i] != i) {
        i = parent[i];
    }
    return i;
}

void union(int[] parent, int[] rank, int x, int y) {
    int xroot = find(parent, x);
    int yroot = find(parent, y);
    if (rank[xroot] < rank[yroot]) parent[xroot] = yroot;
    else if (rank[yroot] < rank[xroot]) parent[yroot] = xroot;
    else {
        parent[yroot] = xroot;
        rank[xroot]++;
    }
}

// parent array initialized as parent[i] = -1 for all i

A ArrayIndexOutOfBoundsException accessing rank array

B NullPointerException when accessing parent array

C No error, code runs correctly

D StackOverflowError due to infinite loop in find

💡 Hint

Check how the parent array is initialized and how find uses it.

If parent[i] is -1 initially, the while loop condition parent[i] != i never becomes false, causing infinite loop and stack overflow.

❓ Predict Output

advanced

Output of MST total weight calculation

What is the output of the following Java code that calculates the total weight of the MST using Kruskal's algorithm?

DSA Java

import java.util.*;

class Edge implements Comparable<Edge> {
    int src, dest, weight;
    public Edge(int s, int d, int w) {
        src = s; dest = d; weight = w;
    }
    public int compareTo(Edge e) {
        return this.weight - e.weight;
    }
}

class Graph {
    int V;
    List<Edge> edges;
    public Graph(int v) {
        V = v;
        edges = new ArrayList<>();
    }
    void addEdge(int s, int d, int w) {
        edges.add(new Edge(s, d, w));
    }
    int find(int[] parent, int i) {
        if (parent[i] == i) return i;
        return find(parent, parent[i]);
    }
    void union(int[] parent, int[] rank, int x, int y) {
        int xroot = find(parent, x);
        int yroot = find(parent, y);
        if (rank[xroot] < rank[yroot]) parent[xroot] = yroot;
        else if (rank[yroot] < rank[xroot]) parent[yroot] = xroot;
        else {
            parent[yroot] = xroot;
            rank[xroot]++;
        }
    }
    int kruskalMSTWeight() {
        Collections.sort(edges);
        int[] parent = new int[V];
        int[] rank = new int[V];
        for (int i = 0; i < V; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
        int totalWeight = 0;
        for (Edge e : edges) {
            int x = find(parent, e.src);
            int y = find(parent, e.dest);
            if (x != y) {
                totalWeight += e.weight;
                union(parent, rank, x, y);
            }
        }
        return totalWeight;
    }
}

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph(5);
        g.addEdge(0, 1, 2);
        g.addEdge(0, 3, 6);
        g.addEdge(1, 2, 3);
        g.addEdge(1, 3, 8);
        g.addEdge(1, 4, 5);
        g.addEdge(2, 4, 7);
        g.addEdge(3, 4, 9);
        System.out.println(g.kruskalMSTWeight());
    }
}

A 16

B 23

C 14

D 20

💡 Hint

Sum the weights of edges chosen by Kruskal's MST.

Edges chosen: (0,1)=2, (1,2)=3, (1,4)=5, (0,3)=6. Total = 2+3+5+6=16. The MST edges are (0,1), (1,2), (1,4), (0,3) total 16.

🚀 Application

expert

Minimum Spanning Tree edge count for disconnected graph

Given a graph with 6 vertices and edges only connecting vertices {0,1,2} and separately {3,4,5}, what is the number of edges in the MST returned by Kruskal's algorithm?

A 5

B 4

C 3

D 2

💡 Hint

MST edges = number of vertices in connected component - 1, summed over all components.

The graph has two disconnected parts each with 3 vertices. Each part's MST has 2 edges. Total MST edges = 2 + 2 = 4.

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