Minimum Spanning Tree Kruskal's Algorithm in DSA Typescript - Execution Trace

Concept Flow - Minimum Spanning Tree Kruskal's Algorithm

Start with all edges sorted by weight

↓

Pick smallest edge not yet chosen

↓

Check if adding edge forms a cycle?

Yes→Discard edge

No↓

Add edge to MST

↓

Repeat until MST has (V-1) edges

↓

Done

Kruskal's algorithm sorts edges by weight and adds them one by one to the MST if they don't form a cycle, until MST spans all vertices.

Execution Sample

DSA Typescript

edges = [(A,B,1), (B,C,3), (A,C,2)]
sort edges by weight
for edge in edges:
  if no cycle with edge:
    add edge to MST

This code sorts edges by weight and adds them to MST if they don't create a cycle.

Execution Table

Step	Operation	Edge Considered	Cycle Check Result	MST Edges	Visual State
1	Sort edges by weight	-	-	[]	Edges sorted: (A,B,1), (A,C,2), (B,C,3)
2	Consider edge	(A,B,1)	No cycle	[(A,B,1)]	MST: A--1--B
3	Consider edge	(A,C,2)	No cycle	[(A,B,1), (A,C,2)]	MST: A--1--B and A--2--C
4	Consider edge	(B,C,3)	Cycle detected	[(A,B,1), (A,C,2)]	MST unchanged: A--1--B and A--2--C
5	Check MST size	Edges in MST = 2	MST complete	[(A,B,1), (A,C,2)]	Final MST: A--1--B and A--2--C

💡 MST has (V-1)=2 edges for 3 vertices, so algorithm stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
edges	[(A,B,1), (B,C,3), (A,C,2)]	[(A,B,1), (A,C,2), (B,C,3)]	[(A,B,1), (A,C,2), (B,C,3)]	[(A,B,1), (A,C,2), (B,C,3)]	[(A,B,1), (A,C,2), (B,C,3)]	[(A,B,1), (A,C,2), (B,C,3)]
MST	[]	[]	[(A,B,1)]	[(A,B,1), (A,C,2)]	[(A,B,1), (A,C,2)]	[(A,B,1), (A,C,2)]
Union-Find sets	[A],[B],[C]	[A],[B],[C]	[A,B],[C]	[A,B,C]	[A,B,C]	[A,B,C]

Key Moments - 3 Insights

Why do we check for cycles before adding an edge?

Because adding an edge that forms a cycle breaks the tree property. See step 4 in execution_table where edge (B,C,3) is discarded due to cycle.

How do we know when to stop adding edges?

We stop when MST has (V-1) edges, where V is number of vertices. Step 5 shows MST has 2 edges for 3 vertices, so algorithm stops.

What data structure helps detect cycles efficiently?

Union-Find (Disjoint Set) tracks connected components. If two vertices are already connected, adding edge creates cycle. See variable_tracker for Union-Find sets.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what edges are in the MST?

A [(A,B,1), (B,C,3)]

B [(A,B,1)]

C [(A,B,1), (A,C,2)]

D []

💡 Hint

Check the MST Edges column at step 3 in execution_table.

At which step does the algorithm detect a cycle?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look at the Cycle Check Result column in execution_table.

If the edge (B,C,3) had weight 0.5, how would the MST change?

A Edge (A,B,1) would be discarded

B Edge (B,C,3) would be added first

C MST would have edges (B,C,3) and (A,C,2)

D No change in MST

💡 Hint

Edges are sorted by weight; check variable_tracker edges after Step 1.

Concept Snapshot

Kruskal's Algorithm for MST:
- Sort all edges by weight ascending
- Use Union-Find to detect cycles
- Add edges if no cycle formed
- Stop when MST has (V-1) edges
- Result is minimum spanning tree connecting all vertices

Full Transcript

Kruskal's algorithm builds a minimum spanning tree by sorting edges from smallest to largest weight. It picks edges one by one, adding them if they don't create a cycle. Cycle detection uses a Union-Find data structure to track connected components. The process stops when the MST contains one less edge than the number of vertices. This ensures the MST connects all vertices with minimum total edge weight.

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