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 Sub...
Proof Every Connected Graph has a Spanning Tree: • Proof: Every Connected...
Kruskal's Algorithm for Minimum Spanning Trees: • Kruskal's Algorithm fo...
#GraphTheory #Math
★DONATE★
◆ Support Wrath of Math on Patreon for early access to new videos and other exclusive benefits: / wrathofmathlessons
◆ Donate on PayPal: 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: crayonangel.bandcamp.com/
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / @emery3050

Пікірлер: 22

  • @soroushfth7055
    @soroushfth70553 жыл бұрын

    this is the best playlist for graph theory, thank you so much

  • @jacobshin4279
    @jacobshin42793 жыл бұрын

    I love these graph videos from a mathematical perspective. There are way more computer science/interview prep videos all over youtube that don't explain WHY an algorithm works or graph property exists and not enough videos like these. Definitely looking forward to your future videos with the proofs.

  • @tusharbarman1924
    @tusharbarman19243 жыл бұрын

    thanks man for making a video on such a short time. Appreciate it

  • @WrathofMath

    @WrathofMath

    3 жыл бұрын

    My pleasure, always glad to turn around requests quickly. I don't get to do it as much these days as I used to. A request was just what I needed to get back into some graph theory lessons!

  • @AnselmoBattisti
    @AnselmoBattisti2 жыл бұрын

    That was the clearest explanation of the Prim 's algorithm I already had in my life! Thanks!

  • @WrathofMath

    @WrathofMath

    2 жыл бұрын

    So glad to hear it! Thanks for watching!

  • @davidshi451
    @davidshi4513 жыл бұрын

    Haha, you always have a knack for covering topics that I just finished learning a month ago. Good video, though. It's also amusing to adapt Prim's to find the maximum spanning tree, and even minimum product spanning tree!

  • @WrathofMath

    @WrathofMath

    3 жыл бұрын

    Thanks, David! Ah well, better than a year ago haha! I've been jonesing to do some more graph theory lately. Will definitely have more on spanning trees soon!

  • @mnnuila
    @mnnuila8 ай бұрын

    Yes CS perspective for all related videos

  • @mahmoudalbahar1641
    @mahmoudalbahar16413 жыл бұрын

    Please ... can you make video about the following question? (What I found at internet is : cardinality of real irrational numbers is equal to cardinality of real numbers so there must be bijection between them but I can't find it by myself or by internet) The question is what is the bijection between real irrational numbers and real numbers?

  • @hadjergr
    @hadjergr3 жыл бұрын

    thank you so much

  • @WrathofMath

    @WrathofMath

    3 жыл бұрын

    My pleasure, thanks for your support! If you're looking for more graph theory, check out my playlist: kzread.info/head/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

  • @PunmasterSTP
    @PunmasterSTPАй бұрын

    Anyone else wonder how things would have played out differently if Katniss hadn't volunteered?

  • @ChocolateMilkCultLeader
    @ChocolateMilkCultLeader3 жыл бұрын

    I can help with the CS perspective

  • @WrathofMath

    @WrathofMath

    3 жыл бұрын

    Thanks, Devansh! I will keep you in mind when the time comes! And anyone watching this video with CS-related questions, I implore you to ask Devansh and not me! 😂

  • @maheshpatel7691
    @maheshpatel76913 жыл бұрын

    Show that height of the cylinder of greatest volume which can be inscribed in a right circular cone of height h and semi vertical angle α is one-third that of the cone and the greatest volume of cylinder is 4πh³tan²α/27. I just wanna know that how much do you rate this one out of 10 for difficulty?

  • @WrathofMath

    @WrathofMath

    3 жыл бұрын

    I'm not sure! I'd have to go through the process of trying to solve it and actually solving it or seeing a solution to have an idea. But scales don't have meaning without context! So a 5 to me might be a 10 to someone with high school level math knowledge/experience, and a 10 to me might be a 5 to someone with more knowledge/skill. Certainly geometry, and 3d geometry, can be deceptively difficult!

  • @maheshpatel7691

    @maheshpatel7691

    3 жыл бұрын

    Yeah. It is the fision of Geometry and diffrentiation. It is from chapter *Application of derivatives*

  • @anushaganesanpmp7602
    @anushaganesanpmp76023 жыл бұрын

    Could you tell when the proof of this algorithm would be explained as i am interested to know why does it work?

  • @WrathofMath

    @WrathofMath

    3 жыл бұрын

    Thanks for watching and I am glad you're eager to know why it works - I think that's the best part! If you want it soon, I'll try to get it done soon - perhaps this weekend! We'll suppose for sake of contradiction that T, a spanning tree produced by Prim's algorithm, is not a minimum spanning tree - and proceed from there!

  • @anushaganesanpmp7602

    @anushaganesanpmp7602

    3 жыл бұрын

    @@WrathofMath thanks !! waiting to see the proof video

  • @infinitymath4342
    @infinitymath4342 Жыл бұрын

    Let T be a tree and e = (u, v) be an edge in T. Then beta(T.e) = beta(T. e),\\ beta(T)-1,\\ beta(T), otherwise. if both u and v are stem vertices; if one of u and v is a leaf and other one is minor stem; otherwise. Can you give me proof of this theorem??