Prim's Algorithm (MST) Visualizer

Prim's Algorithm (MST)

sequentialRAM

A greedy algorithm that finds a Minimum Spanning Tree (MST) for a weighted undirected graph by starting from a root vertex and repeatedly picking the minimum-weight edge connecting a tree vertex to a non-tree vertex.

SIMULATION STEP PROGRESSStep 1 / 1

SPEED (50%)

Code Workspace

1procedure Prim(G, start_node)

2 MST := empty set, visited[start_node] := true

3 PQ.push(all edges from start_node)

4 while PQ is not empty do

5 (u, v, weight) := PQ.pop_min()

6 if visited[v] then continue

7 visited[v] := true

8 add edge (u, v) to MST

9 for each edge (v, w) in G:

10 if not visited[w] then PQ.push(v, w, weight)

11 end while

12end procedure

Currently highlights executing branch

RUNTIME COST METRICS

Comparisons0

Memory Writes0

Memory Reads0

Elements Swapped0

Computational Model:RAM (Single Core)

Theoretical Bound:O(E log V)

Space Complexity:O(V + E)

Communication Cost:0 (Shared Bus)

THEORETICAL ANALYSIS & RESEARCH

Conceptual Focus: A greedy algorithm that finds a Minimum Spanning Tree (MST) for a weighted undirected graph by starting from a root vertex and repeatedly picking the minimum-weight edge connecting a tree vertex to a non-tree vertex.

Real-world Industrial Applications:

Network infrastructure design (telecoms, power grids, water supply)
Cluster analysis in machine learning
Distance-based approximation algorithms