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

Concept Flow - Minimum Spanning Tree Prim's Algorithm

Start with any node

↓

Add node to MST set

↓

Find edges from MST to non-MST nodes

↓

Select edge with minimum weight

↓

Add connected node to MST

↓

Repeat until all nodes in MST

Start from any node, add it to MST. Then repeatedly add the smallest edge connecting MST to a new node until all nodes are included.

Execution Sample

DSA Typescript

const graph = {
  A: {B: 2, C: 3},
  B: {A: 2, C: 1, D: 4},
  C: {A: 3, B: 1, D: 5},
  D: {B: 4, C: 5}
};
// Run Prim's MST starting from A

This code runs Prim's algorithm on a graph with nodes A, B, C, D and weighted edges.

Execution Table

Step	Operation	Nodes in MST	Edges Considered	Selected Edge	Visual MST State
1	Start at node A	[A]	Edges: A-B(2), A-C(3)	Select A-B(2)	A --2-- B
2	Add node B	[A, B]	Edges: B-C(1), B-D(4), A-C(3)	Select B-C(1)	A --2-- B --1-- C
3	Add node C	[A, B, C]	Edges: C-D(5), B-D(4)	Select B-D(4)	A --2-- B --1-- C | 4 D
4	Add node D	[A, B, C, D]	No edges left	None	A --2-- B --1-- C | 4 D
5	All nodes included	[A, B, C, D]	None	Stop	Final MST as above

💡 All nodes are included in MST, algorithm stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
MST Nodes	[]	[A]	[A, B]	[A, B, C]	[A, B, C, D]	[A, B, C, D]
Edges Considered	[]	[A-B(2), A-C(3)]	[B-C(1), B-D(4), A-C(3)]	[C-D(5), B-D(4)]	[]	[]
Selected Edge	None	A-B(2)	B-C(1)	B-D(4)	None	None

Key Moments - 3 Insights

Why do we add edges from all MST nodes, not just the last added node?

Because MST can connect to any node outside MST from any node inside MST, as shown in step 2 where edges from both A and B are considered (execution_table row 2).

Why do we stop when all nodes are included in MST?

Because MST must span all nodes without cycles, so once all nodes are in MST (step 5), no more edges are needed (execution_table row 5).

What if multiple edges have the same minimum weight?

Prim's algorithm can pick any one of them; the MST remains valid. This example picks the first minimum edge found (execution_table rows 1-3).

Visual Quiz - 3 Questions

Look at the execution table, which edge is selected at step 3?

A A-C(3)

B B-C(1)

C B-D(4)

D C-D(5)

💡 Hint

Check the 'Selected Edge' column at step 3 in the execution_table.

At which step does node D get added to the MST?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look at the 'Nodes in MST' column and see when D appears.

If the edge B-D had weight 2 instead of 4, which edge would be selected at step 3?

A B-D(2)

B C-D(5)

C B-C(1)

D A-C(3)

💡 Hint

Compare edge weights at step 3 in the execution_table and consider the minimum.

Concept Snapshot

Prim's Algorithm builds MST by:
- Starting from any node
- Adding the smallest edge connecting MST to new nodes
- Repeating until all nodes included
- Always consider edges from all MST nodes
- Stops when MST spans all nodes

Full Transcript

Prim's algorithm for Minimum Spanning Tree starts from any node and adds it to the MST set. Then it looks at all edges connecting nodes inside MST to nodes outside MST and selects the edge with the smallest weight. The connected node is added to MST. This repeats until all nodes are included. The execution table shows step-by-step which edges are considered and selected, and how the MST grows. Key points include considering edges from all MST nodes, stopping when all nodes are included, and handling ties in edge weights. The variable tracker shows MST nodes and edges considered after each step. The visual quiz tests understanding of edge selection and MST growth.