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 RUclips and this video is in the suggestions. It's like RUclips read my mind.
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
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!
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.
There may be a problem with this approach in some cases, try: var items = [1, 2, 3] var array = [items, [4, 5, 6]] var copy = [...array] items.push(10) console.log(copy) As you can see _copy_ gets modified too, that's because non-primitive values are passed by reference in JS.
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.
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?
you could possibly add those vertices to a priority queue, dependent on weight, and use that queue to check the next vertex that is being used with respect to its weight. Then you could bold that line or change its color, if you're doing it in a visual, then use that implementation to represent the minimum spanning aspect. I hope this helped some.
*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.
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.
//I checked 10 more than times but still dont know why my line function is wrong //plzzzz help me var vertices = []; function setup() { createCanvas(640, 360); } function mousePressed() { var v = createVector(mouseX, mouseY); vertices.push(v); } function draw() { background(51); var reached = []; var unreached = []; for(var i = 0; i < vertices.length; i++) { unreached.push(vertices[i]);//beginning all the vertices are unreached } // reached.push(unreached[0]);//random point for the reached // unreached.splice(0, 1); while(unreached.length > 0) { var record = 100000;//beginning the dist record is 10000 var rIndex; var uIndex; for(var i = 0; i < reached.length; i++) { for(var j = 0; j < unreached.length; j++) { var v1 = reached[i]; var v2 = unreached[j]; var d = dist(v1.x, v1.y, v2.x, v2.y); if(d < record) { record = d;//update the record to make the smallest dist in the record rIndex = i; uIndex = j; } } } stroke(255); strokeWeight(2); line(reached[rIndex].x, reached[rIndex].y, unreached[uIndex].x, unreached[uIndex].y); reached.push(unreached[uIndex]);//random point for the reached unreached.splice(uIndex, 1); }
for(var i = 0; i < vertices.length; i++) { fill(255); stroke(255); ellipse(vertices[i].x, vertices[i].y, 16, 16); } }
That was really nice.. Could you consider implementing the Hungarian algorithm for the assignment problem?? Also thank you for all the helpful videos :)
Prim's is equally good for maze generation. I used prim to generate a MST and then made a game which also showed solution through Dijsktra's Algo, all in Processing.
Thanks again for this great tutorial Daniel? I am just asking myself how the code could be more optimized, because it seems that we're not able to go beyond 900 vertices to draw. Beyond that, the html page just crashes. If anyone have any idea :) Thanks again.
Since we're rerunning the whole algorithm every frame we aren't able to keep up once we get to very large tree sizes. One solution could be to have the code run only when the mouse is pressed. Try throwing in the algorithm code into a mousePressed() function and see if that lets you draw large tree sizes !
interesting video! but one a side note: the video quality is a bit mediocre ... image is not too sharp (especially when you're in front of the drawing board) even in 720p.
Just like you predicted, I'm watching this 7 years later. Great visualization to explain the concept. Thank you Daniel
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 RUclips and this video is in the suggestions. It's like RUclips read my mind.
Not 10 years, but 4 years 😀.
Absolutely love your content bro!
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
I am watching this after 8years since you posted. I am heart broken that it only has 600 or so likes…
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!
15:30 "you watching this 10 years from now"
5
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.
+Asa Taylor Great idea! Was this video helpful / did it make sense?
+Daniel Shiffman made perfect sense! Can it be improved to alleviate the nested loops?
+Daniel Shiffman Ignore my question. I'm sure it's been asked elsewhere.
When something like "Minimum Spanning Tree" pops up, we are at the new gate of a different level.
6:20
let unreached = [...vertices];
Instead of for loop.
There may be a problem with this approach in some cases, try:
var items = [1, 2, 3]
var array = [items, [4, 5, 6]]
var copy = [...array]
items.push(10)
console.log(copy)
As you can see _copy_ gets modified too, that's because non-primitive values are passed by reference in JS.
I like ...
unreached = vertices.splice();
In this case, to copy the array you can use:
arr2 = arr1.slice();
Your tutorials have been really helpful to me! Thanks!
+Hans Willem Gijzel thank you!
+Daniel Shiffman When someone said to use array.concat(), you're supposed to supply an empty array as an argument like array.concat([]).
indeed, thank you!
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.
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?
+monkeytail2002 Yes, it's on my list!
Daniel Shiffman Cool. Will look forward to that.
Could you use an object instead? var vertex = {
v: createVector(mouseX,mouseY),
reached: false
}
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
you could possibly add those vertices to a priority queue, dependent on weight, and use that queue to check the next vertex that is being used with respect to its weight. Then you could bold that line or change its color, if you're doing it in a visual, then use that implementation to represent the minimum spanning aspect. I hope this helped some.
Thanks for your great video,
Is it possible to solve this problem with genetic algorithm?
Uncaught TypeError: Cannot read property 'x' of undefined?
got the same error, did you find how to fix it?
*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.
Thank you as always Simon!!
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.
+endofmysteries glad to hear you liked it, thank you!
//I checked 10 more than times but still dont know why my line function is wrong
//plzzzz help me
var vertices = [];
function setup() {
createCanvas(640, 360);
}
function mousePressed() {
var v = createVector(mouseX, mouseY);
vertices.push(v);
}
function draw() {
background(51);
var reached = [];
var unreached = [];
for(var i = 0; i < vertices.length; i++) {
unreached.push(vertices[i]);//beginning all the vertices are unreached
}
// reached.push(unreached[0]);//random point for the reached
// unreached.splice(0, 1);
while(unreached.length > 0) {
var record = 100000;//beginning the dist record is 10000
var rIndex;
var uIndex;
for(var i = 0; i < reached.length; i++) {
for(var j = 0; j < unreached.length; j++) {
var v1 = reached[i];
var v2 = unreached[j];
var d = dist(v1.x, v1.y, v2.x, v2.y);
if(d < record) {
record = d;//update the record to make the smallest dist in the record
rIndex = i;
uIndex = j;
}
}
}
stroke(255);
strokeWeight(2);
line(reached[rIndex].x, reached[rIndex].y, unreached[uIndex].x, unreached[uIndex].y);
reached.push(unreached[uIndex]);//random point for the reached
unreached.splice(uIndex, 1);
}
for(var i = 0; i < vertices.length; i++) {
fill(255);
stroke(255);
ellipse(vertices[i].x, vertices[i].y, 16, 16);
}
}
That was really nice.. Could you consider implementing the Hungarian algorithm for the assignment problem?? Also thank you for all the helpful videos :)
I stand corrected you had a reason: 11:44
haha, oops, yes.
I was hoping you'd implement (randomized) Kruskal's algorithm too someday. Used in maze generation especially.
Prim's is equally good for maze generation. I used prim to generate a MST and then made a game which also showed solution through Dijsktra's Algo, all in Processing.
This explain like awesome and beautiful....
Github repo not found, can you please upgrade.
404 not found in both links could you PLEASE give me another link?
HERE IS THE NEW CODE : github.com/CodingTrain/Rainbow-Code/tree/master/Tutorials/P5JS/p5.js/09/9.09_p5.js_Minimum_Spanning_Tree
At 7:27 you could just use the JS pop function...
Yes so much simpler :)
Good point!
I think you mean shift(): pop() removes the last element, shift() removes the first element of an array
Where the heck do I find the code for this? Your links are all dead.
Check thecodingtrain.com, apologies, corrected link: github.com/CodingTrain/website/tree/master/Tutorials/P5JS/p5.js/09
Awesome. Thank you!
Nice one ..!!! :) Can we expect T.S.P Algorithm soon ???
Thank you.
Yes, I'll add this to my list!
why not implement it in mousePressed() instead of draw(), and save some CPU cycles
Dan r u still reading comments on u r old video
Dan: yes , I am
Me: how great that u replied to mee
Thanku Dan(◍•ᴗ•◍)❤
Dan : u are welcome😀😍
Tip: since 2015 (ES6) a handy way to copy an array:
arr2 = [...arr1];
Thanks again for this great tutorial Daniel? I am just asking myself how the code could be more optimized, because it seems that we're not able to go beyond 900 vertices to draw. Beyond that, the html page just crashes. If anyone have any idea :) Thanks again.
Since we're rerunning the whole algorithm every frame we aren't able to keep up once we get to very large tree sizes. One solution could be to have the code run only when the mouse is pressed. Try throwing in the algorithm code into a mousePressed() function and see if that lets you draw large tree sizes !
An easier way to copy everything would be
arrayCopy(vertices, unreached);
Not 10 but I am watching them after 5 years..
Hi.
At the end yo did
reached = unreached.concat();
you should have done
reached = vertices.concat();
+alvaro obyrne ah, yes, thank you! Also, see comment below, it should actually be slice().
+Daniel Shiffman I believe both slice and concat work fine
+Daniel Shiffman thank you
interesting video! but one a side note: the video quality is a bit mediocre ... image is not too sharp (especially when you're in front of the drawing board) even in 720p.
+Xeronimo74 Thanks, yes, I'm still working on this new setup. Need to improve the lighting and focus.
record = Infinity;
brillant. thank you so much
+brother rain Thanks for watching!