thank you, i understand both kruskal and prim algorithm now, my lecturer just use lots of mathematical notations to explain it and it barely makes sense but your visualisation and explanation helped, i understood it straight aware, am so prepared for this exam now
would it be reasonable to break from the loop when the list of MST edges will be V - 1 in size? Idea is that we'll need V - 1 edges to connect V vertexes, and we get those edges in a greedy manner. In the video the loop is executed for every single edge.
It depends on how fast you want the implementation to be. The addition of rank adds an optimisation to this algorithm when you do the union of two sets. The RANK is actually just the depth of that node. If we have a set, the larger the depth of a set, the longer the Find(x) method will take because it needs to recursively keep going up to its root node right? So if we do the union of two sets and add a long set to a shorter one we've increased the overall depth of the new union of that tree by 1 right? Therefore, complexity is getting worse. However, if when we combine sets together with the union, we check whether x's depth is less than y, we know that x is a shorter set than y so we should assign x root's parent to y's root so thus we have added a shorter set to a longer set. As a result we do not increase the depth of the resultant union set and do not worsen complexity. Hope this made sense
In that line he use the constructor of vector which takes 2 iterator(t is iterator to begining of array and t + sizeof(t) / sizeof (t[0]) is end of array)
I notice a lot of advanced material in your code. For eg, the use of 'vector' (which I in my limited knowledge am assuming to be a template of some sort) also in your disjoint set video the use of hash table was a bit beyond my comparison. Is there any book or material I can refer to to extend my knowledge of C++ ? Thanks in advance.
Hey, sorry for late reply, but a vector is part of C++'s standard template library, or STL. Vectors in C++ work much like the arrays you know from other languages, but are not fixed in size, and have some special functions you can use. You can read more about it here: www.cplusplus.com/reference/vector/vector/
Can i get a link for the program you are using to do the nodes and graphs in this video? or i can realize that it's a freaking powerpoint and im slow as shit... LOL great vid btw
You are amazingly good. I wish you could post programming interview problems: edit distance, knapsack problem, permutation of a string, combination, kth smallest element, longest palindromic substring, shortest path, ... Thanks in advance.
find(x) finds the root node of that set. So if you pass in 'K' which is a member of a set, it will recursively look at it's parent until it's parent is itself and thus must be the root node and returns that value.
Great video; however, your Union function is not correct. The Union should match the leader of one point (via the find function) to the other point. It's irrelevant as to which point should be the "main" leader.
thank you, i understand both kruskal and prim algorithm now, my lecturer just use lots of mathematical notations to explain it and it barely makes sense but your visualisation and explanation helped, i understood it straight aware, am so prepared for this exam now
Explained in a very simple manner.
unparalleled explanation. thank you for walking through the psuedo code as well!!
All your videos are concise and clear. Thanks so much for your work!
Great video man, you're a solid programmer!
He works at apple
You english and illustration are so good!
Simple and straightforward. Very helpful, thanks so much!
I don't understand I used the code in the page and it didn't work, what do I have to add, the libraries?
You are Awesome Bro🔥🔥
Nice video, I like how you include the implementation.
thanks a lot ... you are a great teacher.
We are greatful to you.
Very helpful demonstration, thanks a lot!
Bo Qian my man thank you for the HD video that makes my eyes oh so happy and infusing me with the MST * fist bump *
The "minimum spanning she" will haunt me for the rest of my life
thanks for including the codes and explaining!
thanx for such a great demo...
Your videos are awesome, cheers mate!
Thank you so much, very well put together!
would it be reasonable to break from the loop when the list of MST edges will be V - 1 in size? Idea is that we'll need V - 1 edges to connect V vertexes, and we get those edges in a greedy manner. In the video the loop is executed for every single edge.
Thank you so much. It is very helpful.
What if we remove the RANK think from this program? Will it make any difference in the output?
I had the exact same question.
It depends on how fast you want the implementation to be. The addition of rank adds an optimisation to this algorithm when you do the union of two sets. The RANK is actually just the depth of that node.
If we have a set, the larger the depth of a set, the longer the Find(x) method will take because it needs to recursively keep going up to its root node right? So if we do the union of two sets and add a long set to a shorter one we've increased the overall depth of the new union of that tree by 1 right? Therefore, complexity is getting worse.
However, if when we combine sets together with the union, we check whether x's depth is less than y, we know that x is a shorter set than y so we should assign x root's parent to y's root so thus we have added a shorter set to a longer set. As a result we do not increase the depth of the resultant union set and do not worsen complexity.
Hope this made sense
kindly someone tell how to figure out the time complexity of prims and kruskal algo
Amazing, thank you a lot for explanation!
you saved me!!! I was struggling for days!!
great work ..thanks :)
will be "Looting" for you,, :P
I still not understand code "(t, t + sizeof(t) / sizeof (t[0]) )" means, any idea ?
In that line he use the constructor of vector which takes 2 iterator(t is iterator to begining of array and t + sizeof(t) / sizeof (t[0]) is end of array)
tks for your comment :D
I notice a lot of advanced material in your code. For eg, the use of 'vector' (which I in my limited knowledge am assuming to be a template of some sort) also in your disjoint set video the use of hash table was a bit beyond my comparison. Is there any book or material I can refer to to extend my knowledge of C++ ?
Thanks in advance.
Hey, sorry for late reply, but a vector is part of C++'s standard template library, or STL. Vectors in C++ work much like the arrays you know from other languages, but are not fixed in size, and have some special functions you can use. You can read more about it here: www.cplusplus.com/reference/vector/vector/
感谢大神的讲解
Thanks for the video. It was crisp. How may I find the slides?
Can i get a link for the program you are using to do the nodes and graphs in this video? or i can realize that it's a freaking powerpoint and im slow as shit... LOL great vid btw
Incredible video... Thanks
Thanks mate. Great videos!
Best explanation
You are amazingly good. I wish you could post programming interview problems:
edit distance, knapsack problem, permutation of a string, combination, kth smallest element, longest palindromic substring, shortest path, ... Thanks in advance.
does this use path compression?
what does the find function do?
find(x) finds the root node of that set.
So if you pass in 'K' which is a member of a set, it will recursively look at it's parent until it's parent is itself and thus must be the root node and returns that value.
Clear and concise thanks!
does this work? like if you ran it?
Can this be used to Find The Maximum Spanning Tree? Can the code be altered and then find the maximum spanning tree?
ya just sort it based on greatest to least and not least to greatest as he does
is MCST same as MST
+Raymond Berry ya if you mean minimum cost spanning tree
Great video; however, your Union function is not correct.
The Union should match the leader of one point (via the find function) to the other point. It's irrelevant as to which point should be the "main" leader.
brilliant !! and off course thanks a lot. :)
great lecture! thanx
Thank you very much. This was very helpful!
Congratulations boy. Thanks.
Language is C or C++?
c++
your video saved my day 👍🏻btw it would be nice if u post your code/collections on github as well
Awesome Geek!!!
Thank you
can you give me this source
code???
you are the boss..thanks a lot
please help us with c language also.
Learn Python
thank you so much, man!
very helpful, thank you :)
Thanks a 'loot' ;)
U should tell the dis joint set in this vdoe also
the code does not work
Thank you so much.
showing an algorithm and demonstrating some code with it too? what is this magic?
Thank you so much :)
thanks a lot man
4:14
change the speed to 1.25
it helps a lot
Need the source code link that you are using in this vedio
excellent
thanx for ths video
Thanks man :)
thanks
Thanks sir
NICE
"loot"
the first part is very bad explained
Thank you, this was very helpful!
Thank you very much!
Thank you very much :)