Kruskal's Algorithm for Minimum Spanning Trees (MST) | Graph Theory
ฝัง
- เผยแพร่เมื่อ 15 เม.ย. 2021
- We go over Kruskal'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 Kruskal'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 Kruskal'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.
#GraphTheory #Math
Spanning Subgraphs: • What is a Spanning Sub...
Proof Every Connected Graph has a Spanning Tree: • Proof: Every Connected...
Prim's Algorithm for Minimum Spanning Trees: • Prim's Algorithm for M...
Graph Theory Playlist: • Graph Theory
★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
![แม่กลองสองใจ - ซีแกรม โตเกียว มิวสิค [ OFFICIAL MUSIC VIDEO ]](http://i.ytimg.com/vi/GSQfVjcr_f4/mqdefault.jpg)
I like how Kruskal's Algorithm almost seems like a game, at least, compared to the previous videos with proofs in them. Thanks again for making such an amazing playlist!
Hi Shaun, I really like your graph theory play list. I just watched all your video till this one, but i notice you didn't talk about Dijksta algorithm. I wonder can you make another video to explain it and add you the graph theory playlist? I guess it will help a lot of students like me. : D and thank you all of your effort!
You can keep explaining graph theory algorithms, that's very interesting (also I wonder how why this algorithm is correct)
Thanks for watching Cédric! We'll definitely be looking at more graph theory algorithms as time goes on, and the proofs of Prim's algorithm and Kruskal's algorithm will hopefully be coming soon!
Thank you so much!!!
You're welcome!
Thank you so much. This is also important for competitive programming
My pleasure! Thanks for watching, looking forward to doing the proof!
Out of curiosity, have you done any competitive programming yourself?
Excellent Explanation Sir...Can u plz make some videos regarding algebraic graphs Sir...it will be more helpful Sir... Thank u
thank you, best explaination
Thanks for watching!
Much needed video!Thanks! also please post Chinese postman theorem too..
Thanks for watching! And by Chinese postman theorem you mean a particular algorithm for solving the postman problem?
@@WrathofMath yup
My go-to
Thank you!
Hello, have you made the video of the proof that Kruskal's algorithm generates an MST? I can't find the video. If you haven't made it, would you consider making it?
Hello Shaun, could please also suggest a good graph theory textbook to follow along with your excellent lectures ? It would be quite helpful. Or possibly notes of lectures for regular revision.
Thanks for watching Abhishek! And absolutely, my go-to is "A First Course in Graph Theory" by Chartrand and Zhang. The structure of my graph theory playlist is largely based on this book.
@@WrathofMath Thanks a lot for this great help!!
Can you solve 100 algebra questions in one take please
Haha, that could be fun! What sorts of algebra questions would you want to be included?
@@WrathofMath polynomials, functions and equations