← visual-cs

Prim's Algorithm

Graph · MST
Click Randomize to generate a graph, then Run to find the MST.

Status

Phase Idle
Nodes in MST —
MST Edges —
MST Total Weight —
Candidates —

MST Edges Added

    Legend

    Node in MST
    Current frontier node
    Unvisited node
    MST edge (selected)
    Candidate edges (frontier)
    Unselected edges

    Algorithm

    Prim's builds an MST by greedily expanding a visited set. Starting from any node, at each step it picks the minimum-weight edge crossing the cut between visited and unvisited nodes and adds its endpoint to the tree.

    Time: O(E log V) with a min-heap.
    Space: O(V + E)