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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of MST edges after Kruskal's algorithm

What is the output of the edges included in the MST after running Kruskal's algorithm on the given graph?

DSA Typescript

interface Edge {
  src: number;
  dest: number;
  weight: number;
}

const edges: Edge[] = [
  {src: 0, dest: 1, weight: 10},
  {src: 0, dest: 2, weight: 6},
  {src: 0, dest: 3, weight: 5},
  {src: 1, dest: 3, weight: 15},
  {src: 2, dest: 3, weight: 4}
];

// After running Kruskal's MST, print edges in MST as array of [src, dest]
// in the order they are added.

// Assume vertices are 0 to 3.

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

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

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

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

💡 Hint

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

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

Pick edges in this order if they don't form a cycle:

• (2,3) weight 4 - add
• (0,3) weight 5 - add
• (0,2) weight 6 - would form cycle with (2,3) and (0,3), skip
• (0,1) weight 10 - add
• (1,3) weight 15 - would form cycle, skip

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

🧠 Conceptual

intermediate

Number of edges in MST for a graph with V vertices

For a connected graph with V vertices, how many edges will the Minimum Spanning Tree (MST) contain?

A V - 1

B V

C V + 1

D V * 2

💡 Hint

Think about how many edges connect all vertices without cycles.

An MST connects all vertices with the minimum number of edges to avoid cycles.

For V vertices, MST always has exactly V - 1 edges.

🔧 Debug

advanced

Identify the error in this Kruskal's algorithm snippet

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

DSA Typescript

class DisjointSet {
  parent: number[];
  constructor(n: number) {
    this.parent = Array(n).fill(-1);
  }
  find(x: number): number {
    if (this.parent[x] < 0) return x;
    return this.find(this.parent[x]);
  }
  union(a: number, b: number): void {
    const rootA = this.find(a);
    const rootB = this.find(b);
    if (rootA !== rootB) {
      this.parent[rootB] = rootA;
    }
  }
}

// Usage omitted for brevity

A Runtime error due to union method missing return statement

B TypeError because parent array is not initialized

C No error, code runs correctly

D Stack overflow due to missing path compression in find()

💡 Hint

Consider what happens if find() calls itself repeatedly without optimization.

The find() method uses recursion but does not update parent[x] to root, so deep recursion can cause stack overflow.

This is a common issue without path compression optimization.

🚀 Application

advanced

Minimum cost to connect all cities using Kruskal's MST

Given the weighted edges between cities, what is the minimum total cost to connect all cities using Kruskal's algorithm?

DSA Typescript

const edges = [
  {src: 0, dest: 1, weight: 7},
  {src: 0, dest: 3, weight: 5},
  {src: 1, dest: 2, weight: 8},
  {src: 1, dest: 3, weight: 9},
  {src: 1, dest: 4, weight: 7},
  {src: 2, dest: 4, weight: 5},
  {src: 3, dest: 4, weight: 15},
  {src: 3, dest: 5, weight: 6},
  {src: 4, dest: 5, weight: 8},
  {src: 4, dest: 6, weight: 9},
  {src: 5, dest: 6, weight: 11}
];

// Cities numbered 0 to 6
// Calculate total weight of MST

A 35

B 40

C 39

D 37

💡 Hint

Sort edges by weight and pick edges without cycles until all cities connected.

Sorted edges by weight: (0,3)=5, (2,4)=5, (3,5)=6, (0,1)=7, (1,4)=7, (1,2)=8, (4,5)=8, (1,3)=9, (4,6)=9, (5,6)=11, (3,4)=15.

Pick edges in this order if they don't form a cycle:

• (0,3) weight 5 - add
• (2,4) weight 5 - add
• (3,5) weight 6 - add
• (0,1) weight 7 - add
• (1,4) weight 7 - add (connects {0,1,3,5} and {2,4})
• (1,2) weight 8 - cycle, skip
• (4,5) weight 8 - cycle, skip
• (1,3) weight 9 - cycle, skip
• (4,6) weight 9 - add

Edges in MST: (0,3), (2,4), (3,5), (0,1), (1,4), (4,6)

Total weight = 5 + 5 + 6 + 7 + 7 + 9 = 39

📝 Syntax

expert

Identify the syntax error in this TypeScript Kruskal's implementation snippet

Which option correctly identifies the syntax error in the following code snippet?

DSA Typescript

const edges = [
  {src: 0, dest: 1, weight: 4},
  {src: 1, dest: 2, weight: 8},
  {src: 2, dest: 3, weight: 7},
];

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

for (const edge of edges) {
  if (disjointSet.find(edge.src) !== disjointSet.find(edge.dest)) {
    disjointSet.union(edge.src, edge.dest)
    mstEdges.push(edge)
  }
}

A Arrow function in sort() missing curly braces

B disjointSet is not declared or initialized

C mstEdges is not declared or initialized

D Missing semicolon after sort() call

💡 Hint

Check if all variables used are declared before use.

The code uses disjointSet without declaring or initializing it, causing a ReferenceError.

Missing semicolons or arrow function braces are not syntax errors in this context.

mstEdges usage without declaration would also cause error, but question focuses on disjointSet.

Practice

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

easy

A. To find the minimum spanning tree of a connected weighted 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 the purpose of Kruskal's Algorithm

   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 algorithms

   Unlike shortest path or cycle detection algorithms, Kruskal's focuses on building a minimum spanning tree.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

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

2. Which of the following TypeScript code snippets correctly initializes the edges array for Kruskal's Algorithm?

easy

A. const edges: number[][] = [0, 1, 10, 1, 2, 5, 0, 2, 15];

B. const edges = {0:1:10, 1:2:5, 0:2:15};

C. const edges: [number, number, number][] = [[0, 1, 10], [1, 2, 5], [0, 2, 15]];

D. const edges: Array<number> = [[0, 1, 10], [1, 2, 5], [0, 2, 15]];

Solution

1. Step 1: Check the correct TypeScript tuple array syntax

   Edges should be an array of tuples, each tuple having three numbers: [node1, node2, weight]. const edges: [number, number, number][] = [[0, 1, 10], [1, 2, 5], [0, 2, 15]]; uses this syntax correctly.

2. Step 2: Identify incorrect syntax in other options

   const edges = {0:1:10, 1:2:5, 0:2:15}; uses invalid object syntax. const edges: number[][] = [0, 1, 10, 1, 2, 5, 0, 2, 15]; is a flat array, not an array of tuples. const edges: Array<number> = [[0, 1, 10], [1, 2, 5], [0, 2, 15]]; uses wrong type annotation (Array<number> instead of tuple array).

3. Final Answer:

   const edges: [number, number, number][] = [[0, 1, 10], [1, 2, 5], [0, 2, 15]]; -> Option C

4. Quick Check:

   Tuple array syntax = const edges: [number, number, number][] = [[0, 1, 10], [1, 2, 5], [0, 2, 15]]; [OK]

Hint: Use tuple arrays for edges: [node1, node2, weight][] [OK]

Common Mistakes:

• Using flat arrays instead of tuples
• Wrong object syntax for edges
• Incorrect type annotations

3. What will be the output edges of the minimum spanning tree after running Kruskal's Algorithm on this graph?

const edges: [number, number, number][] = [[0, 1, 4], [0, 2, 3], [1, 2, 1], [1, 3, 2], [2, 3, 4], [3, 4, 2], [4, 5, 6]];

medium

A. [[0, 1, 4], [1, 3, 2], [3, 4, 2], [4, 5, 6]]

B. [[1, 2, 1], [1, 3, 2], [3, 4, 2], [0, 2, 3], [4, 5, 6]]

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

D. [[0, 1, 4], [0, 2, 3], [1, 2, 1], [4, 5, 6]]

Solution

1. Step 1: Sort edges by weight

   Sorted edges: [1,2,1], [1,3,2], [3,4,2], [0,2,3], [0,1,4], [2,3,4], [4,5,6]

2. Step 2: Pick edges without forming cycles until all nodes connected

   Pick [1,2,1], [1,3,2], [3,4,2], [0,2,3], and [4,5,6]. These connect all nodes with minimum total weight without cycles.

3. Final Answer:

   [[1, 2, 1], [1, 3, 2], [3, 4, 2], [0, 2, 3], [4, 5, 6]] -> Option B

4. Quick Check:

   Edges sorted + no cycles = [[1, 2, 1], [1, 3, 2], [3, 4, 2], [0, 2, 3], [4, 5, 6]] [OK]

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

Common Mistakes:

• Choosing heavier edges first
• Including edges that form cycles
• Missing edges to connect all nodes

4. Identify the error in this TypeScript snippet implementing Kruskal's Algorithm:

const edges: [number, number, number][] = [[0,1,1],[1,2,2],[0,2,3]];
const parent = [0,1,2];
function find(x: number): number {
  if(parent[x] === x) return x;
  return find(parent[x]);
}
function union(a: number, b: number) {
  const rootA = find(a);
  const rootB = find(b);
  if(rootA !== rootB) parent[rootB] = rootA;
}
// Missing sorting of edges before processing

medium

A. The union function incorrectly assigns parent

B. The find function does not implement path compression

C. The parent array should be initialized with -1

D. The edges array is not sorted by weight before processing

Solution

1. Step 1: Check Kruskal's Algorithm requirements

   Kruskal's requires edges to be sorted by weight ascending before union-find operations.

2. Step 2: Identify missing sorting step

   The code comment notes missing sorting; without sorting, MST may not be minimal.

3. Final Answer:

   The edges array is not sorted by weight before processing -> Option D

4. Quick Check:

   Sorting edges first is essential [OK]

Hint: Always sort edges by weight before union-find steps [OK]

Common Mistakes:

• Skipping edge sorting
• Ignoring path compression (optional)
• Incorrect parent initialization

5. Given a graph with vertices 0 to 4 and edges:

[[0,1,10],[0,2,6],[0,3,5],[1,3,15],[2,3,4]]

Use Kruskal's Algorithm to find the total weight of the minimum spanning tree.

hard

A. 19

B. 20

C. 25

D. 15

Solution

1. Step 1: Sort edges by weight

   Sorted edges: [2,3,4], [0,3,5], [0,2,6], [0,1,10], [1,3,15]

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

   Pick [2,3,4], [0,3,5], [0,2,6] connect nodes 0,2,3. Then pick [0,1,10] to connect node 1. Total weight = 4+5+6+10 = 25. But this forms a cycle because 0,2,3 are connected. Instead, pick [2,3,4], [0,3,5], [0,1,10]. Then pick [0,2,6] creates cycle. So skip [0,2,6]. Next pick [1,3,15] is heavier and unnecessary. So MST edges: [2,3,4], [0,3,5], [0,1,10]. Total weight = 4+5+10=19.

3. Final Answer:

   19 -> Option A

4. Quick Check:

   Sum of MST edges weights = 19 [OK]

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

Common Mistakes:

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