Disjoint Sets using union by rank and path compression Graph Algorithm
HTML-код
- Опубликовано: 29 сен 2024
- Design disjoint sets which supports makeSet, union and findSet operations. Uses union by rank and path compression for optimization.
github.com/mis...
github.com/mis...
/ tusharroy25
All
students are saved by Indian Tutors on RUclips. Thanks India !!
🇮🇳 I love my India!
Allah saves us all.....
nice video to learn how to represent disjoint sets and operations performed on it
unbelievable clear and easy to understand.
Ótima explicação! Great work again.
Thank You for awesome explaination
Beautiful, thanks
Great introduction! :D
At 7:51 shouldn't the rank for data element 6 be 1?
I swear, every time I see Tushar walk in front of the camera I can't help but smile.
Thanks for being such a friendly and righteous dude.
0:05 What is Disjoint Set?
Disjoint Set is data structure that supports the following operations:
a. make set: create a set with only 1 element in it
b. union: take 2 different sets and merge them in one
c. find set: to return the identity of a set
Identity of a set is usually an element of the set that acts as a representative for it
Use Cases:
1. Kruskal's Algorithm
2. finding cycle in an undirected graph
0:38 Implementations:
1. using rank and path
- uses a tree
- node: int rank
int data
node parent
a. make set:
1. initialize n nodes with data and rank=0
2. make parent of all nodes point to the node itself
b. find set(node):
1. dfs to a node that points to itself (root)
2. path compression: node.parent=root
3. return root
c. union(a, b):
1. A=find set(a),
B=find set(b)
2. if A==B => already in the same set
3. if(A.rank>B.rank) make A te parent of B and increments its rank by 1
vice-verse
11:07 Time and Space Complexity
for m operations and n elements
Space: O(n)
Time: O(m.α(n)) ≈ O(4m) ≈ O(m)
11:57 Code
if A.rank > B.rank you shouldn't increment the rank. when both the sets are of same depth/rank only you have to increment the rank.
if (A.rank > B.rank) B.parent = A;
else if (B.rank > A.rank) A.parent = B;
else { // both are equal so pick any
B.parent = A; // A is the parent now
A.rank++;
}
@@reshmaarul8637 thanks man, lemme edit that
When the path compression happens in findSet, there should be a change in rank in this case as well. Rank of root with data = 1 shouldl be 2. Although there will be no problem in this particular example but if instead of union(7, 13), it was union(7, 14) then due to path compression the rank of both the trees would change(the root with data 1 should be 2 and the root with data 11 should be 1) and after setting the parent of 11 as 1, the final rank of root 1 should be 2. But in this code, the rank is not getting updated which might lead to a problem in further unions which may involve a node in this component.
Non-root ranks don't matter which Tushar mentions, since we'll only be merging using the rank of the parents
Just a small little note: when he's saying 2 goes to zero (10:20), it should have been 1. He was reading the new rank of one which was zero (I just don't want anyone to be confused). Excellent video and explanation! Thanks a lot!
2 goes to real parent only when will perform find operation ,then all the member in the path will goes to main parent directly . this is will not the case for union. check code once
i have understand the whole video till 12 minutes then java came with hashmap and killed my C ++.
there is unordered_map in c++. duckduckgo.com/?q=unordered_map+c%2B%2B&t=canonical&atb=v55-1&ia=web
Why he set a map to a hashmap, instead of defining the variable as a hashmap to begin with?
Then I must say you're not good in C++ also.
@@a55tech Map is an interface in java.util. You can consider an interface as a blueprint of classes. HashMap is a class that implements the interface.
Since every HashMap is a Map, his way of writing isn't incorrect. He could have done what you're saying, but his method required him to type 4 less letters :)
I once gave a lecture in university and I thanked the Indian students for their help
Can you please make a video explaining amortized analysis?
I'm confused with the RANK. It seems that rank is determined by the higher ranked set when performing the union rank, i.e., union(set_m rank1, set_n rank0) results to be rank1. Does that indicate rank won't change as we keep attaching rank0 set to another set?
me too
@@achuachu6296 Rank will change iff we try to union two elements of different sets having same rank . else the higher raked set will always be the parent of lower ranked set.
10:56 isn't the rank of node 4 becomes 1 (depth of the tree after path compression) ?
at around 9:45, why does the rank of node 1 become 0?
Rank does not need to be accurate.
because for non-root nodes it doesn't matter what the rank is... The rank of the root node is the one that is important.
Rank should be 1 as we can see in java code.
I think its a mistake
Yes, it is a mistake. The rank would not change.
7:42 Rank of 6 will be (1) itself, only 4's rank increased to 2, but then as sir said, it won't matter what is the rank at the non-root node, we're never going to see them, so doesn't matter if its 1 or 0 or any other number. We're concerned only about 4's rank.
Best Data Structures and Algorithms videos on youtube!!!!!!!!!!
Not anymore. Abdul Bari is here to transform everything. Check his channel. He doesnt stammer and talks slowly and his videos are crisp. No offense to Tushar though
Abdul bari is a beauty... He is a gem💎💎💎😍😍😍
@@AbhishekKumar-im2xd yes!!
@@blasttrash Tushar Roys explanation is top notch...
@@rohitk472not really, he jumps directly into say choosing dynamic programming or assuming that its greedy without explaining the reasoning behind it. There are many newer youtubers who explain things better.
Thank you for your video, now it makes so much more sense to me! I have a question what if the findset number is the root, does the map just not change at all?
yes, cause when we will get the node and the parent and compare them then if the condition will give true cause they are equal and then we will simply return. Though I know you must not need this reply after 5 years but replying just to make you nostalgic
people like you make this world a better place!
Why isn't (3) the end rank of 4 after the final merge?
Rank only increases if two sets of equal rank merge. Since the set represented by 4 had a rank of (2) and the set represented by 1 had a rank of (1), the rank of 4 did not need to increase.
But why so? Why does the rank increase by 1 only when sets of equal rank merge?
If I am correct that is simply a stipulation of the algorithm. That is to say, only increase rank when a union has occurred between sets of equal rank.
Now if you have 2 tree having same rank..and you want to make one as parent then automatically the one which is going to be the parent must be 1 more than the child. So that's why it is +1
This video is amazing. It's explained so clearly, and it was a great idea to showcase the theory first, and then demonstrate the implementation. Great work man!
Rank is not optimal, let's assume one node A has 1000 children, one node B has 1 child, both of them have the same rank, you could choose B as new root since it's random, now all the 1000 nodes below A need travel two steps to root B and one node under A travels one step to B, but if choose A as root is optimal since all 1000 nodes only travel one step to new root A and only one node travels two steps to A. So if change the rank to weight as how many descendants the node has will be the best.
this video was uploaded 5 years ago ,but still best 👍🏻 as compares with others
So much good explanation 🤗
9:03 rank of node 4 in second component should also have been 1 after path compression at 8:17 and therefore either component could be merged to the other while performing union(3, 7) at 9:03
great explanation, thanks
I think rank of parent 1 should be incremented in else loop in java code from line 63 to 65.
Thanks! This is helping me get through my cs class in college
17:30 why the output is 4?
yeah, it should be 1
10,20,30,40,50,60,70,80,90
Union ( 10,30) union (20,40) union(50,90) union (40,60) union(10,70) union(40,70) union(10,90)
Can any one tell me the answer of this problem please
I already watched videos on union by rank and didn't quite understand why we're incrementing rank for a few cases and why not for other cases. Your explanation made it so clear! We'll increment rank only if both the sets are of the same rank, otherwise, we just make a union 🙂
At the step of merging the tree of 1
The whiteboard explanation 7:40 does not match the code 12:40:
There is no reduction of rank back to 0 after union operation. This should not matter, but perhaps make it consistent.
There's a bug in the code 12:40, where the else section does not update the rank if parent2 rank is > parent1 rank.
Tushar videos are fast and great but in this video another thing to notice is : 12.05 Tushar talks in native language and now we know he is desi guy :)
Ye hago k ads bhi na🤣😂
Thank you dude what great explanation. Excellent video !!!
That findSet function with the path compression is so fucking clever, nice dude!
Abdul Bari explains that rank should be the total number of nodes in a set, including itself. But he uses array to store nodes. Are you sure about rank?
Can you please upload the implementation of Ds with C++ below
??
Why 4 is the representative of the combined set when 1 is smaller than 4? Please make me understand
Why doesnt the rank for 1 change at 6:08
Good question :) The rank changes only in one scenario: when we want to merge 2 parents who have the same rank, the new parent's rank will be increased by one. In that scenario, the rank for 1 was 1 and 3's rank was 0. Since their rank is different, 1's rank stays the same.
thank you very much,you are explaining the material very good
Why didn't you change the parents rank in the second set when you did path compression?
And thank you so much for this video it helped me in the middle of the night to understand this concept ❤
This is the best explanation available on internet
Thanks for the video. Isn't it 1 should be shown at the end?
There is no base condition in the long findSet function. Would that lead to error
Brilliant, really helps to watch your videos before reading about the topic at hand! Ty very much, keep up the good work :)
Indian so great, they dominates the world of IT
this is the best Disjoint Set Union video in the whole youtube !!! at 7:52 rank of the ( 6 ) should be 1
Doesn't matter, we aren't really concerned about ranks of nodes other than parent's
Thank you so much, Ray William Johnson!
This video is criminally underrated
When using path compression along with union by rank, the rank might be incorrect on application of the path compression algorithm. I have found union by size and path compression to be logically correct where path compression doesn't affect union by size at all.
Any thoughts on this ? Would appreciate if anybody can point out if I'm missing out on anything for Union by Rank + Path compression
At 8:35 after making path compression doesn't the rank of the root need to be decreased from 2 to 1?
Lets call the root of a tree r. Generally, it is not trivial to determine whether r's rank decreased. That's because there might be still some other paths in the tree, rooted at r, maintaining r's rank as before. So if a path gets compressed in a tree, you cannot claim the root's rank has decreased.
I agree with you @vahid sanel, but then when we perform union operation on two sets, both of whose rank is decreased, we won't be making the optimal choice for root always, right?
Love your videos man!
Absolutely love your videos. I'm currently preparing for my interviews and your videos have been the go-to for me so far! Keep up the great work and thanks a million.
after 5 year also your videos are great,,,
i was not able to understand clearly in any video then i came here, , FINALYY DONE
Why do the rank not change on FIND-SET operation?
8:40 Rank of 4 is clearly = 1 unit.
Find Set does not change the root. The rank of non-root don't matter.
Tushar thanks, I finally learned all about ranking union. Very happy for your video congratulations, I will follow your channel now.
Why we are finding parents in union..
Does it not increase the complexity of union from O(1) to O(logn)
we have already calculated the parent in find set of the corresponding node
so no need to calc. in union function
I' am i correct???
I think in the step where node having value 1 comes under 4 as parent, 4's rank should be increased to 3 from 2, but you kept it 2 only and decreased the rank of 1 from 1 to 0. Please clear it.
At 10:19,you said 2 followed the parent 0 to reach 4 but it should be like 2 followed parent 1 to reach 4.Please correct me if I am wrong.
helped me out big time once again. thank you!
very good, very helpful, and understandable for me even though english isn't my first language. thanks for sharing!
confused about the rank update part. also, shouldn't we update the rank when necessary when we each time call find function?
but when we have union(1,5) then we will take only 1 findset and 5 or we will take 1,2,3,4,5. ?
Two doubts:
1. I think Rank is Height not the Depth?
2. And Path Compression is done only after calling the FindSet() or it's done immediately once union is done?
+Tushar Roy Exactly, it's the definition of height of the root right?
best explanation, made it simple!
I think instead of creating Nodes to store parent and ranks we can directly use Arrays or HashMap(for random order elments) right for storing parents and rank?
At 9:00 when 7 directly starts pointing to 4 instead of 6, shouldn't the rank for 4 decrease by 2. Instead of 2 shouldn't it be 1?
Thsnks sir for amazing tutorial
At around 8:20, before the path of 7 is compressed, the rank of 6 should be (1) instead of (0).
Anyone else hear the fart around 10:36 ?
Perhaps the most helpful disjointed sets video I've come across so far, thank you!
why cant we directly make their parents same when we are doing union. it will take O(1) time .
At 7:41, node 6 is marked with rank of 0. But 6 has a child (node 7). So shouldn't the rank of 6 become 1?
Rank of non root does node not matter, as after path reduction it is eventually going to point to the root.
at 8:47 , why the rank for node 4 is still 2? I'm confused with the ranks
confused about rank part...
why 10:02 the node 1 has zero depth?
why doesn't rank of one go down too 2 from 3 at 15:20 in the video?? Great Video Thank You so much!!!
why ain't we modifying rank of nodes each time when compression is performed? Btw excellent video..:)
U save a lot of time... Tqs man.
What happens if we apply only path compression ?? Amazing video!!
When you run through the path compression logic, shouldn't the rank decrease for each disjoint set when there is an optimization to be had? For example, when you first merge 2 sets, you might have a rank of 3. After you use findSet(), doesn't the rank fall back down to 1?
Has a duster on one hand but...
shoudn't the rank of node 4 after last union operation be 3 instead of 2 at 10:00 ?
do you choose the representative of two merged sets randomly in this video? wanna know if that's important or just a trivial matter
oh sorry I didn't enter that union by rank part when I left this stupid comment, so it's basically decided by comparing their ranks.
Interesting data structure :)
Basically path compression will occur only during search for the first time
excellent video..cleared all doubts in very less time...thanks a ton sir...
at 8:49, doesnt 4 become rank 1 again due to path compression?
Your videos are the best!
I had the rank question too. If you have it pay close attention to the explanation at 15:21
Doesn't the rank of the tree that has 4 as a parent/representative decrease to (1) when you do path compression in that tree when we made 7 point to 4 instead of 6?
+Hajer Karoui 8:40
Just awesome. I did not get this much of understanding from ny book. thanks a lot.
only if you walked through the code of every problem like you did in this one!! Great work Tushar! You're still helping people after 6 years!!
Will not the rank of parents change after path compression happens?
nice video.........has definately helped me in understanding the concept of disjoint set