• Prim’s Algorithm

Prim’s Algorithm

1. Start with an arbitrary vertex and greedily add closest vertices
2. Similar to Dijkstra’s algo, but $dist[v]$ is the weight of the edge connecting $v$ to the MST instead of the distance from $s$.

Runtime: $O(|E| \log |V|)$ (Fibonacci-heaps)

Back to Minimum Spanning Tree

Data Structures and Algorithms Table of Contents

---

anusha-murali.github.io