| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectionvi [2012/03/01 03:43] – [A simple Data Structure for Union-Find] mugabej | courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectionvi [2012/03/01 03:54] (current) – [Implementing Kruskal's Algorithm] mugabej |
|---|
| ==== A simple Data Structure for Union-Find ==== | ==== A simple Data Structure for Union-Find ==== |
| | |
| * Maintain an Array ** Component ** of size n that contains the name of the set currently containing each element | >>>>>>>>>>>>>>>>> Maintain an Array ** Component ** of size n that contains the name of the set currently containing each element\\ |
| * Let S = {1,...,n} | >>>>>>>>>>>>>>>>> Let S = {1,...,n}\\ |
| * Component[s] = the name of set containing s | >>>>>>>>>>>>>>>>> Component[s] = the name of set containing s\\ |
| * To implement ** MakeUnionFind(S) **: | >>>>>>>>>>>>>>>>> To implement ** MakeUnionFind(S) **:\\ |
| * Set up an array and initialize it to Component[s] = s for all s in S | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Set up an array and initialize it to Component[s] = s for all s in S\\ |
| * With this operation, Find(v) is done in O(1) time | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> With this operation, Find(v) is done in O(1) time\\ |
| * But Union(A,B) can take O(n) time with this operation(-->We have to update the values of Component[s] for all elements in A and B) | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> But Union(A,B) can take O(n) time with this operation(-->We have to update the values of Component[s] for all elements in A and B)\\ |
| * To improve on this bound of Union(A,B): | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> To improve on this bound of Union(A,B):\\ |
| * Maintain the list of elements in each set | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Maintain the list of elements in each set\\ |
| * Choose the name for the union to be the name of one of the sets, so we only update Component[s] for s in the other set | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Choose the name for the union to be the name of one of the sets, so we only update Component[s] for s in the other set\\ |
| * If the other set is big, name the union to be the name of that set and update Component[s] for s in the smaller set | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> If the other set is big, name the union to be the name of that set and update Component[s] for s in the smaller set\\ |
| * Maintain an Array Size of length n | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Improvements:\\ |
| * Size[A] = the size of A | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Maintain an Array Size of length n\\ |
| * So when a Union(A,B) operation is needed, we use the name of the larger set for the union and update Component for only the smaller set | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Size[A] = the size of A\\ |
| * However, we still have a O(n) time even after the improvements | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> So when a Union(A,B) operation is needed, we use the name of the larger set for the union and update Component for only the smaller set\\ |
| | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> However, we still have a O(n) time even after the improvements\\ |
| |
| * So, overall, Find(u) takes O(1) time,MakeUnionFind(A,B) takes O(n) time and any sequence of k Union operations takes at most O(klogk) time | >>>>>>>>>>>>>>>>> So, overall, Find(u) takes O(1) time,MakeUnionFind(A,B) takes O(n) time and any sequence of k Union operations takes at most O(klogk) time with this simple implementation of the algorithm.\\ |
| \\ | \\ |
| ==== A Better Implementation for Union-Find ==== | ==== A Better Implementation for Union-Find ==== |
| >>>>>>>>>>>>>>>>> Find(u) takes O(logn) time \\ | >>>>>>>>>>>>>>>>> Find(u) takes O(logn) time \\ |
| |
| | ==== Implementing Kruskal's Algorithm ==== |
| |
| | >>>>>>>>>>>>>>>>> T = {} |
| | >>>>>>>>>>>>>>>>> foreach (u ∈ V) make a set containing singleton u |
| | >>>>>>>>>>>>>>>>> for i = 1 to m |
| | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> (u,v) = ei |
| | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> if (u and v are in different sets) |
| | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> T = T ∪ {ei} |
| | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> merge the sets containing u and v |
| | >>>>>>>>>>>>>>>>> return T |
| | |
| | ( The above algorithm, is from the class discussion) |
| | \\ |
| | \\ |
| | Kruskal's algorithm implemented as above runs in O(mlogn) time. |
| | \\ |
| | \\ |
| | This section was also interesting, although it contained some long proofs. I give it an 8/10 |
