12. Greedy Algorithms: Minimum Spanning Tree

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
Instructor: Erik Demaine

In this lecture, Professor Demaine introduces greedy algorithms, which make locally-best choices without regards to the future.

License: Creative Commons BY-NC-SA

[freccia]

Prim's algorithm starts 42:20
Kruskal's algorithm : 1:06:00

[sgzerolc]

correctness for Prim's algorithm 52:01
correctness for Kruskal's algorithm 1:15:35

[neerajkrishna]

Erik Demaine is one of the best Instructors!

[trinhngocdieu]

Really appreciate the MIT resource on this. Erik is an amazing teacher!

[mohansinghrawat]

Sir Erik you are best at teaching.. thankyou for the support...

[parkamark]

I've just utilised Kruskal's algorithm to solve a real-world problem we were facing at the company I work at. It is a very simple and elegant algorithm to implement. As of writing, it's solved our requirement of finding a spanning tree of a connected cyclic graph containing around 80 nodes, but we may have future instances with even more nodes (hundreds!). In our setup, none of the edges have weights so it just picks a random edge each time, effectively producing an arbitrary spanning tree upon each invocation of the problem, which is fine for what we need it for.

Excellent video!

[hannahdo]

That was a valuable lecture... But that chalkboard almost gave me mild asthma 😂

[LF]

Im in the top 500 universities, and still finding youtube helping me more then my prof....

[ryancocuzzo]

Wow. This guy is good. Very impressed with this lecture.

[inadaizz]

I really enjoy this professor. Thank you MIT and Professor Demaine.
Regards from The University of Toledo.

[PeterHoward-rp]

I really like the old style by using chalks and blackboards especially their snappy sounds

[scrappy-mvp]

The proof of the greedy choice property is incorrect. You can’t exchange any edge crossing the cut with e to get the MST but you have to find the edge that is part of the cycle when you add e. And this uses the property of a cut that if an edge that crosses a cut is part of a cycle then there’s another edge of that cycle that crosses the cut too. And this cycle edge may or may not be the current edge we’re trying to exchange in the Tree.

[hemantdhanuka]

Totally Impressed with U sir , why i find u so late... u are fanstastic teacher

[fracturedude]

@27:05 in what situation is w(T') < w(T* - e)? Isn't w(T') = w(T* - e)?

[TheKarateKidd]

This guy is a pro at writing on a chalkboard.

[shivanshmishra]

First time in my life loving the proofs

[pourkavoosmedicalllcpourka]

What an excellent lecturer! Very clear and concise.

[kentemershonyucra]

Its correct proof the optimal substructure only by cut y paste that show in Cormen in programming dynamic chapter, if T* = T contracting a edge, and T = w(edge) + T*, suppose that T is minimum, if T* is not minimum, I can copy a minimum spanning tree T** here and, we get a T not is minimum, what is a contradiction.

[eiebfiebrkcfne]

33:04 exchange argument (cut and paste argument)

[soumadipranjanbiswas]

Thank You. Sir, you are an amazing teacher. Thank you for your videos, they are so clear and easy to understand. However, I'm a little confused still about the running time of Prim's. Would anyone be able to explain how you can decrease a key in a Fibonacci heap in constant time? If you were implementing prim's with a regular min-heap, would the running time change from O(Vlog(V) + E) to O(Vlog(V) + Elog(V)) to reflect the slower decrease key operation? (normal heaps, as I understand, take log(n) time to decrease the value of a key, correct?)