9.9: Minimum Spanning Tree (Prim's Algorithm) - p5.js Tutorial

This video covers the computational geometry "minimum spanning tree" problem, and walks through the JavaScript code for a solution known as "prim's algorithm."

Help us caption & translate this video!

[beknazbaktygulov]

Just like you predicted, I'm watching this 7 years later. Great visualization to explain the concept. Thank you Daniel

[kevnar]

Just yesterday, I was thinking about how to do a minimum-spanning tree. I wasn't sure how to get it done. The next morning I sit down at YouTube and this video is in the suggestions. It's like YouTube read my mind.

[hussainnagaria]

Not 10 years, but 4 years 😀.
Absolutely love your content bro!

[TheChodex]

Hehe i just learned this month ago in Discrete Mathematics class so i paused video at beginning tried it for myself first, succeeded and now i am watching your video to see how you solved it (maybe to see how to organize code and learn a new idea) :D

[badunius_code]

15:30 "you watching this 10 years from now"

5

[siddharthchauhan]

I am watching this after 8years since you posted. I am heart broken that it only has 600 or so likes…

[goldthumb]

When something like "Minimum Spanning Tree" pops up, we are at the new gate of a different level.

[ericrovell]

Thanks for such an amazing tutorial!
I think it is better to use js value Infinite for the record instead of the big number. I checked it out now it works :D

Thanks again! You are the best teacher I ever had!

[AsaTaylor]

I am currently studying Prims maze algorithms and would enjoy seeing you illuminate the subject with your special teaching magic. I think it compliments p5's graphical nature.

[hanswillem]

In this case, to copy the array you can use:

arr2 = arr1.slice();

Your tutorials have been really helpful to me! Thanks!

[bennybrouwer]

Hi Dan, since you are more and more going into maths and stats, I dare to ask you about the "shortest path" theory, or the "traveling salesman". From the days the internet did not yet exist. Your presentation here is teasing and I'm learning a lot but . . but . . I still have friends doing deliveries by van or truck going from street to street and address to home number. Maybe you are ahead of me and already have some lectures here - - in that case I'm interested.

[endofmysteries]

this was great! I always love learning a new algorithm! thanks for taking the time to teach this!

I can't understand why there's currently 1 Downvote on this video... I don't see any reason someone would do that. savage.

[arturdomanski]

6:20
let unreached = [...vertices];
Instead of for loop.

[mehediabdullah]

This explain like awesome and beautiful....

[periklisrips]

That was really nice.. Could you consider implementing the Hungarian algorithm for the assignment problem?? Also thank you for all the helpful videos :)

[monkeytail]

Hi Dan, I asked you a question regarding mouseClicked and sound playing/pausing on an earlier video and I was wondering if you were going to cover the sound side of things in a series of videos?

[SimonTiger]

*Correction:* The MST problem does not allow any loops (like A->B, B->C, C->D, D->A again.) So the solution at 2:30 is wrong!
In fact, _no wonder it does that_, because Prim's Algorithm will never find a loop. Here's why:


Let's suppose that it could find a loop (let's say, a loop of 4, so A->B, B->C, C->D, D->A again, but this argument would work the same each way.)
Ok, so it will start from A, and mark it as reached.
It will check A against B, C and D, find B, and mark B as reached.
Then, it will check A against C and D, and B against C and D. and it will find that it should connect B and C, and mark C as reached.
Then, it will check A, B and C all against D, and find that it should connect C and D, and mark D as reached.
But now, we reach a problem. It _will not_ connect D and A, because both are already reached!


Why was it designed like that? Because that's what the problem says! It's a Minimum Spanning _Tree_, so it can't have any loops.


So there you go, that's why Prim's algorithm will not find a loop.

[omidkhajehdehi]

Thanks for your great video,
Is it possible to solve this problem with genetic algorithm?

[shridharmamidalaa]

Nice one ..!!! :) Can we expect T.S.P Algorithm soon ???

Thank you.

[neamhariri]

is there a way i can do it with "already weighted" graph ? instead of setting x and y ?
i have vertex and edge and graph object