Eager Prim's Minimum Spanning Tree Algorithm | Graph Theory

[@jamesbon68]

Great video! I came over from the Lazy Prim's video and just want to share that O(ElogE) is actually equals to O(ElogV). A complete graph can have V(V - 1)/2 edges. Representing this in big O notation is O(V^2). So O(ElogE) = O(ElogV^2) = O(E(2logV)) = O(ElogV). The eager method is definitely faster but the time complexity is actually the same. 😄

[@sanjarcode]

but space in eager is V, so definitely better.

[@ikechinwankwo7993]

Thanks I have been so confused about this as well!

[@Barabara100]

The quality of the videos is awesome...

[@Chichichifan]

Thank for your video !!! It hlep me lot!!!

[@abhijit-sarkar]

4:25 - "While the IPQ is not empty and a MST has not been formed" - If the IPQ holds no more than V entries, it is not possible for it to be non-empty but a MST has been formed. By definition, the MST includes all the vertices in the graph, so, in order to include all vertices, the IPQ must be completely drained.

[@ghostfjdgcsusvsgsj]

excellent explanation like always

[@halyph]

hello William, I like your visualization, looks cool ! Do you use something like PowerPoint for graph drawing ?

[@WilliamFiset-videos]

Just Keynote, nothing too fancy :) Slides should be available through links in the description.

[@amanbhatia7442]

Hi William, I really enjoyed your Data Structures beginning to advanced series. Gave me a refresher and also a clear understanding of using those Data structures. Will you be doing a structured series for Algorithms(Beginner to advanced) just like the data structures one? Also could you please also make a video on what are the current interview trends at companies like google,microsoft,amazon and facebook. What is expected of a grad student to know, when they apply for an internship?

[@WilliamFiset-videos]

Hi Aman, thanks for the ideas. I'm tackling CS topics one at a time In hopes of covering as much ground as possible.

[@amanbhatia7442]

@@WilliamFiset-videos Looking forward to your videos William. Data structures series was truly excellent. Now I'm moving on to Algorithms, referring CLRS and your videos for those.

[@DavidDLee]

None of C++ STL, Java Collections and Python Collections have Indexed Priority Queue. Golang has a 'Fix' method, which allows updating a value, but it does not have an index function to find the value and it's not obvious how to find items after a Fix call, which takes an index as input.

[@deepakganesh811]

Is there a way to use Prim's like algorithm for an unweighted graph? Since, comparing edge costs in PQ might not make sense when the weights are all same. (The context is the case of using Manhattan distance to calculate edge costs between neighbouring nodes in a map with grids of cells)

[@WilliamFiset-videos]

Even if all the weights are the same Prims will find a valid MST

[@antoine2571]

If you want to find the MST of an unweighted graph, just DFS.

[@sepehrkhodadadi9403]

Spectacular 😍

[@kunal_chand]

Amazing. Big fan !!!

[@matts8911]

incredible

[@Esthicodes]

Hello, William, is MST algorithm related to AI?

[@prasadborse2161]

So its basically the bellman ford algorithm

[@marvelfan5444]

Hey William, great video! Would you mind adding both the Prim's MST to the Udemy Graph theory course please. They're not on there

[@WilliamFiset-videos]

Ohh I think you're right! Will add them later today