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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kruskal's MST edges selection

What edges are included in the MST after running Kruskal's algorithm on this graph?

DSA Javascript

const edges = [
  {u: 0, v: 1, w: 10},
  {u: 0, v: 2, w: 6},
  {u: 0, v: 3, w: 5},
  {u: 1, v: 3, w: 15},
  {u: 2, v: 3, w: 4}
];

// Kruskal's algorithm picks edges in ascending order of weight
// and adds them if they don't form a cycle.
// What edges are in the MST (list of [u,v])?

// Output format: JSON array of edges, e.g. [[0,3],[2,3],[0,1]]

A [[0,1],[0,2],[1,3]]

B [[2,3],[0,3],[0,1]]

C [[0,3],[2,3],[1,3]]

D [[0,2],[2,3],[0,1]]

💡 Hint

Sort edges by weight and pick edges that don't form cycles.

Kruskal's algorithm sorts edges by weight: (2,3)=4, (0,3)=5, (0,2)=6, (0,1)=10, (1,3)=15.

It picks (2,3), then (0,3), then (0,2) would form a cycle, so skip it, then (0,1) is safe.

Edges in MST: (2,3), (0,3), (0,1).

🧠 Conceptual

intermediate

Why does Kruskal's algorithm use a disjoint set?

What is the main purpose of using a disjoint set (union-find) data structure in Kruskal's algorithm?

A To quickly check if adding an edge creates a cycle

B To sort edges by weight efficiently

C To store the graph adjacency list

D To find the shortest path between two nodes

💡 Hint

Think about how Kruskal avoids cycles.

The disjoint set helps track which nodes are connected.

Before adding an edge, it checks if the two nodes belong to the same set.

If yes, adding the edge creates a cycle, so it is skipped.

🔧 Debug

advanced

Identify the error in this Kruskal's implementation snippet

What error will this code produce when running Kruskal's algorithm?

DSA Javascript

function find(parent, i) {
  if (parent[i] === i) return i;
  return find(parent, parent[i]);
}

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

// Missing initialization of parent and rank arrays

const edges = [
  {u: 0, v: 1, w: 1},
  {u: 1, v: 2, w: 2}
];

// Attempt to run union-find without initializing parent and rank
union(parent, rank, 0, 1);

A No error, runs correctly

B TypeError: parent is not iterable

C ReferenceError: parent is not defined

D RangeError: Maximum call stack size exceeded

💡 Hint

Check if variables are declared before use.

The code calls union(parent, rank, 0, 1) but parent and rank are never declared or initialized.

This causes a ReferenceError because parent is undefined.

❓ Predict Output

advanced

Final MST weight after Kruskal's algorithm

What is the total weight of the MST formed by Kruskal's algorithm on this graph?

DSA Javascript

const edges = [
  {u: 0, v: 1, w: 4},
  {u: 0, v: 2, w: 3},
  {u: 1, v: 2, w: 1},
  {u: 1, v: 3, w: 2},
  {u: 2, v: 3, w: 4},
  {u: 3, v: 4, w: 2},
  {u: 4, v: 5, w: 6}
];

// MST weight is sum of selected edges' weights

A 10

B 9

C 12

D 14

💡 Hint

Pick edges in ascending order without cycles and sum weights.

Edges sorted by weight: (1,2)=1, (1,3)=2, (3,4)=2, (0,2)=3, (0,1)=4, (2,3)=4, (4,5)=6.

Pick (1,2), (1,3), (3,4), (0,2), (4,5) without cycles.

Total weight = 1+2+2+3+6 = 14, but (0,1) or (2,3) would create cycles.

Actually, MST edges: (1,2), (1,3), (3,4), (0,2), (4,5) sum to 14.

But we must check carefully: (0,2) connects 0 and 2, (1,2) connects 1 and 2, (1,3) connects 1 and 3, (3,4) connects 3 and 4, (4,5) connects 4 and 5.

Sum is 1+2+2+3+6=14.

But option D is 10, so re-check.

Actually, (4,5) weight 6 is large, maybe we can avoid it?

Graph has 6 nodes (0 to 5), MST must have 5 edges.

Edges chosen: (1,2)=1, (1,3)=2, (3,4)=2, (0,2)=3, (4,5)=6 total 14.

So correct answer is 14.

🧠 Conceptual

expert

Why is Kruskal's algorithm efficient with sparse graphs?

Why does Kruskal's algorithm perform better on sparse graphs compared to dense graphs?

A Because it sorts edges and processes fewer edges in sparse graphs

B Because it uses adjacency matrix which is smaller in sparse graphs

C Because it uses BFS which is faster on sparse graphs

D Because it ignores edge weights in sparse graphs

💡 Hint

Think about the number of edges and sorting cost.

Kruskal's algorithm sorts all edges by weight.

Sparse graphs have fewer edges, so sorting is faster.

Also, fewer edges mean fewer union-find operations.

Practice

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

easy

A. To find the minimum spanning tree of a graph

B. To find the shortest path between two nodes

C. To detect cycles in 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, not Kruskal's.

3. Final Answer:

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

4. Quick Check:

   Minimum Spanning Tree = Kruskal's Algorithm goal [OK]

Hint: Kruskal connects all nodes with least total edge weight [OK]

Common Mistakes:

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

2. Which of the following is the correct way to sort edges by weight in JavaScript for Kruskal's Algorithm?

easy

A. edges.sort((a, b) => a.weight * b.weight);

B. edges.sort((a, b) => b.weight - a.weight);

C. edges.sort((a, b) => a.weight + b.weight);

D. edges.sort((a, b) => a.weight - b.weight);

Solution

1. Step 1: Understand sorting for MST

   Kruskal's Algorithm requires edges sorted in ascending order by weight to pick smallest edges first.

2. Step 2: Check JavaScript sort syntax

   Using edges.sort((a, b) => a.weight - b.weight); sorts edges from smallest to largest weight correctly.

3. Final Answer:

   edges.sort((a, b) => a.weight - b.weight); -> Option D

4. Quick Check:

   Sort ascending by weight = edges.sort((a, b) => a.weight - b.weight); [OK]

Hint: Sort edges ascending by weight using (a,b) => a.weight - b.weight [OK]

Common Mistakes:

• Sorting descending instead of ascending
• Using addition or multiplication in sort callback
• Not returning a number in sort function

3. Consider the following edges of a graph:
const edges = [ {from: 'A', to: 'B', weight: 1}, {from: 'B', to: 'C', weight: 4}, {from: 'A', to: 'C', weight: 3}, {from: 'C', to: 'D', weight: 2} ];
After applying Kruskal's Algorithm, which edges will be included in the MST?

medium

A. [{A-B,1}, {A-C,3}, {B-C,4}]

B. [{A-B,1}, {C-D,2}, {A-C,3}]

C. [{A-B,1}, {C-D,2}, {B-C,4}]

D. [{B-C,4}, {A-C,3}, {C-D,2}]

Solution

1. Step 1: Sort edges by weight ascending

   Sorted edges: (A-B,1), (C-D,2), (A-C,3), (B-C,4)

2. Step 2: Pick edges without forming cycles

   Pick A-B (1), then C-D (2), then A-C (3). Adding B-C (4) would form a cycle, so skip it.

3. Final Answer:

   [{A-B,1}, {C-D,2}, {A-C,3}] -> Option B

4. Quick Check:

   Edges with smallest weights and no cycles = [{A-B,1}, {C-D,2}, {A-C,3}] [OK]

Hint: Pick edges ascending weight, skip if cycle forms [OK]

Common Mistakes:

• Including edges that form cycles
• Not sorting edges before selection
• Choosing heavier edges unnecessarily

4. The following code snippet tries to implement Kruskal's Algorithm but has a bug:

const edges = [
  {from: 'A', to: 'B', weight: 1},
  {from: 'B', to: 'C', weight: 2},
  {from: 'A', to: 'C', weight: 3}
];

edges.sort((a, b) => a.weight - b.weight);

const mst = [];
const visited = new Set();

for (const edge of edges) {
  if (!visited.has(edge.from) || !visited.has(edge.to)) {
    mst.push(edge);
    visited.add(edge.from);
    visited.add(edge.to);
  }
}
console.log(mst);

What is the main issue with this code?

medium

A. It does not correctly check for cycles, so MST may be incorrect

B. The edges are not sorted properly

C. The visited set is not initialized

D. It uses an array instead of a linked list for MST

Solution

1. Step 1: Analyze cycle detection logic

   The code uses a visited set to check if nodes are visited, but this does not detect cycles correctly in Kruskal's Algorithm.

2. Step 2: Understand correct cycle detection

   Kruskal's requires a Union-Find or Disjoint Set data structure to detect cycles properly, not just visited nodes.

3. Final Answer:

   It does not correctly check for cycles, so MST may be incorrect -> Option A

4. Quick Check:

   Cycle detection needs Union-Find, not visited set [OK]

Hint: Use Union-Find to detect cycles, not visited nodes [OK]

Common Mistakes:

• Using visited set for cycle detection
• Ignoring cycle checks
• Assuming sorting fixes all issues

5. You have a graph with vertices ['A', 'B', 'C', 'D', 'E'] and edges:

const edges = [
  {from: 'A', to: 'B', weight: 1},
  {from: 'B', to: 'C', weight: 3},
  {from: 'A', to: 'C', weight: 2},
  {from: 'C', to: 'D', weight: 4},
  {from: 'D', to: 'E', weight: 5},
  {from: 'B', to: 'E', weight: 6}
];

Using Kruskal's Algorithm with a Union-Find structure, what is the total weight of the minimum spanning tree?

hard

A. 10

B. 15

C. 12

D. 16

Solution

1. Step 1: Sort edges by weight ascending

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

2. Step 2: Pick edges without cycles using Union-Find

   Pick A-B(1), A-C(2), B-C(3) forms cycle, skip B-C. Pick C-D(4), D-E(5). Total weight = 1+2+4+5 = 12.

3. Final Answer:

   12 -> Option C

4. Quick Check:

   Sum of MST edges = 12 [OK]

Hint: Sum smallest edges without cycles using Union-Find [OK]

Common Mistakes:

• Including edges that form cycles
• Adding all edges without checking
• Misordering edges before selection