Brendan Ang

Search

Search IconIcon to open search

Prim's Algorithm

Last updated Nov 8, 2022 Edit Source

# Prim’s Algorithm

## General Idea It is a greedy algorithm to generate a [Minimum Spanning Tree](Notes/Minimum%20Spanning%20Tree.md). 1. Select the minimum weight edge from tree vertex to fringe vertex 2. Update the fringe vertex distances with the minimum weight edge and the parent node for this min weight edge 3. Repeat until all vertices are in the tree ## Pseudocode ![](https://i.imgur.com/GI9xa3E.png)

# Complexity

# Proof

Combine with proof of

# Examples