Prim's MST

Grows a minimum spanning tree outward from one vertex, repeatedly taking the cheapest edge that leaves the tree. Compare it with Kruskal: Prim keeps one connected blob and expands it, Kruskal merges scattered fragments — different pictures, identical total weight.

Best

O(E log V)

Average

O(E log V)

Worst

O(E log V)

Space

O(V)