Minimum Spanning Tree Kruskal's Algorithm in DSA Javascript - 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?

↓

Add edge to MST

↓

Repeat until MST has (V-1) edges

↓

Done

Kruskal's algorithm sorts edges by weight, then adds edges one by one to the MST if they don't create a cycle, until MST has all vertices connected.

Execution Sample

DSA Javascript

edges = [('A','B',1),('B','C',3),('A','C',2),('C','D',4)]
Sort edges by weight
Initialize MST = []
For each edge in sorted edges:
  If edge does not form cycle:
    Add edge to MST
Return MST

This code sorts edges by weight and adds them to the 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	-	-	[]	[]
2	Consider edge	('A','B',1)	No cycle	[('A','B',1)]	A--1--B
3	Consider edge	('A','C',2)	No cycle	[('A','B',1),('A','C',2)]	A--1--B | 2 C
4	Consider edge	('B','C',3)	Cycle detected	[('A','B',1),('A','C',2)]	A--1--B | \ 2 3 C
5	Consider edge	('C','D',4)	No cycle	[('A','B',1),('A','C',2),('C','D',4)]	A--1--B | \ 2 3 C--4--D
6	MST complete with 3 edges	-	-	[('A','B',1),('A','C',2),('C','D',4)]	Final MST

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

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
MST Edges	[]	[('A','B',1)]	[('A','B',1),('A','C',2)]	[('A','B',1),('A','C',2)]	[('A','B',1),('A','C',2),('C','D',4)]	[('A','B',1),('A','C',2),('C','D',4)]
Edges Considered	[('A','B',1),('B','C',3),('A','C',2),('C','D',4)]	[('A','C',2),('B','C',3),('C','D',4)]	[('B','C',3),('C','D',4)]	[('C','D',4)]	[]	[]
Cycle Check Result	-	No	No	Yes	No	-

Key Moments - 3 Insights

Why do we skip the edge (B,C,3) even though it connects two vertices?

Because adding (B,C,3) would create a cycle with edges (A,B,1) and (A,C,2). This is shown in step 4 of the execution_table where cycle check returns 'Yes' and the edge is skipped.

How do we know when to stop adding edges to the MST?

We stop when MST has (V-1) edges, where V is the number of vertices. In this example, with 4 vertices, we stop after adding 3 edges as shown in step 6.

What does the 'Cycle Check Result' mean in the execution table?

'No cycle' means the edge can be safely added without creating a loop. 'Cycle detected' means adding the edge would create a loop, so we skip it. This prevents cycles in MST.

Visual Quiz - 3 Questions

Look at the execution table, what is the MST after step 3?

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

B [('A','B',1)]

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

D [('A','B',1),('A','C',2),('B','C',3)]

💡 Hint

Check the MST Edges column at step 3 in the execution_table.

At which step does the algorithm detect a cycle and skip an edge?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at the Cycle Check Result column in the execution_table.

If the edge (C,D,4) was removed from the edges list, what would happen to the MST?

A Algorithm would add (B,C,3) to avoid cycle

B MST would be the same with 3 edges

C MST would have only 2 edges and not connect all vertices

D Algorithm would stop early with incomplete MST

💡 Hint

Check variable_tracker for MST Edges and consider how many edges are needed to connect 4 vertices.

Concept Snapshot

Kruskal's Algorithm for MST:
- Sort all edges by weight ascending
- Add edges one by one if they don't form a cycle
- Use Union-Find or cycle check to detect cycles
- Stop when MST has (V-1) edges
- Result is a tree connecting all vertices with minimum total weight

Full Transcript

Kruskal's algorithm builds a minimum spanning tree by sorting edges by weight and adding them if they don't create cycles. It stops when the MST has one less edge than the number of vertices. The execution table shows each step: sorting edges, checking cycles, adding or skipping edges, and the MST's state. Key points include skipping edges that cause cycles and stopping after enough edges are added. The variable tracker shows how MST edges grow and which edges are considered. This method 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 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