prims
WeightedGraphWe choose an arbitrary start vertex, and attempt to sequentially reduce the distance to all vertices. After attempting to find the lowest weight edge to connect all vertices, we return our MST
Implemented using a binary heap
@complexity
O(E lg V )
Prim’s algorithm runs in O(V) · T_extractMin + O(E) · T_decreaseKey
| Priority Queue | T_extractMin | T_decreaseKey | Total |
|---|---|---|---|
| Array | O(V ) | O(1) | O(V 2) |
Binary heap |
O(lg V ) | O(lg V ) | O(E lg V ) |
| Fibonacci heap | O(lg V ) (amortized) | O(1) (amortized) | O(E + V lg V ) |
@paramgraph
WeightedGraph@params
string@returns
WeightedGraph