Prim's Algorithm for Minimum Spanning Trees (MST) | Graph Theory

We go over Prim's Algorithm, and how it works to find minimum spanning trees (also called minimum weight spanning trees or minimum cost spanning trees). We'll also see two examples of using Prim's algorithm to find minimum spanning trees in connected weighted graphs.

This algorithm is one way to solve the problem of finding a spanning tree of minimum weight in a connected weighted graph. The weight of a subgraph of a weighted graph is the sum of the weights of the subgraph's edges. So, among all spanning trees of a graph G, if we use Prim's algorithm to find a minimum spanning tree T of G, it will be a spanning tree of minimum weight/minimum cost. Note that neither spanning trees nor minimum spanning trees are necessarily unique.

Spanning Subgraphs:    • What is a Spanning Subgraph? | Graph ...  
Proof Every Connected Graph has a Spanning Tree:    • Proof: Every Connected Graph has a Sp...  
Kruskal's Algorithm for Minimum Spanning Trees:    • Kruskal's Algorithm for Minimum Spann...  

#GraphTheory #Math

★DONATE★
◆ Support Wrath of Math on Patreon for early access to new videos and other exclusive benefits:   / wrathofmathlessons  
◆ Donate on PayPal: https://www.paypal.me/wrathofmath

Thanks to Robert Rennie, Barbara Sharrock, and Rolf Waefler for their generous support on Patreon!

Thanks to Crayon Angel, my favorite musician in the world, who upon my request gave me permission to use his music in my math lessons: https://crayonangel.bandcamp.com/

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● Facebook:   / wrathofmath  
● Twitter:   / wrathofmathedu  

My Music Channel:    / @emery3050