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

Support the production of this course by joining Wrath of Math to access all my graph theory videos!
   / @wrathofmath  
🛍 Check out the coolest math clothes in the world: https://mathshion.com/

Graph Theory course:    • Graph Theory  
Graph Theory exercises:    • Graph Theory Exercises  

Get the textbook! https://amzn.to/3HvI535

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 Theory  
Proof Every Connected Graph has a Spanning Tree:    • Proof: Every Connected Graph has a Spannin...  
Kruskal's Algorithm for Minimum Spanning Trees:    • Kruskal's Algorithm for Minimum Spanning T...  

★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

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