DAA Greedy MST 27

MST (Prim’s Algorithm)

Greedy idea: grow a tree from a start node by repeatedly taking the cheapest edge crossing the cut (implemented as a min-priority queue of key[v]).

← Index ↗ Kruskal (26)

Graph (Plotly)

Speed
Preset Start node Show weights
MST edges
0
Total weight
0
Extract-min
—
Priority Queue (frontier)
—
We display the queue as a sorted list by key[v] (conceptual min-heap).
key[] and parent[]
—
v key[v] parent[v] in MST?
Pseudocode (Prim)
Line: —

Step Explanation

Click Start, choose a start node, then press Step to extract-min and relax its neighbors.

Notes: why it works + complexity
  • Cut property: the cheapest edge crossing the cut (MST vs non-MST) is safe.
  • key[v] stores best known edge weight to connect v to the current tree.
  • With a binary heap, runtime is typically O(E log V).

Course designed by Abhay Singh Bisht. Connect on LinkedIn →