Eager Prim's Minimum Spanning Tree Algorithm | Graph Theory

Подписаться 179 тыс.

Просмотров 25 тыс.

50% 1

Prim's Minimum Spanning Tree (MST) Algorithm
Algorithms repository:
github.com/wil...
Video slides:
github.com/wil...
Indexed priority queue data structure:
• Indexed Priority Queue...
Previous video (lazy Prim's): • Prim's Minimum Spannin...
Next video (source code video): • Video
===================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix

Опубликовано:

7 сен 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 22

@jamesbon68 2 года назад

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.

@Barabara100 3 года назад

The quality of the videos is awesome...

@halyph 5 лет назад

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

@WilliamFiset-videos 5 лет назад

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

@Chichichifan 6 месяцев назад

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

@abhijit-sarkar 8 месяцев назад

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.

@DavidDLee 2 месяца назад

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.

@amanbhatia7442 5 лет назад

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 5 лет назад

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 5 лет назад

@@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.

@ghostfjdgcsusvsgsj Год назад

excellent explanation like always

@sepehrkhodadadi9403 3 года назад

Spectacular 😍

@kunal_chand 5 лет назад

Amazing. Big fan !!!

@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