Prim's Algorithm.md

title	date	lastmod
Prim's Algorithm	2022-11-08	2022-11-21

Prim's Algorithm

<iframe width="560" height="315" src="https://www.youtube.com/embed/cplfcGZmX7I" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> ## 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 

Complexity

Proof

Combine with proof of

Examples