Prim's MST
Grows a minimum spanning tree from a seed node, always absorbing the cheapest edge that leaves the tree. Think of it as "expand the blob greedily".
- Category
- Graphs
- Time complexity
- O(E log V)
- Space complexity
- O(V)
Pseudocode
tree ← {start}
add cheapest edge leaving tree
(node joins, repeat)
MST when all nodes in
Reference implementation
tree = {start}
while tree != V:
e = cheapest edge leaving tree
tree.add(e.other_end)