Graph
Union-find
Quick-find
- Data structure.
- Integer array id[] of size N.
- Interpretation: p and q are connected if they have the same id.
- Find. Check if p and q have the same id.
- Union. To merge components containing p and q, change all entries with id[p] to id[q].
- Quick-find defect.
- Union too expensive (N steps).
- Trees are flat, but too expensive to keep them flat.
Quick-Union
- Data structure.
- Integer array id[] of size N.
- Interpretation: id[i] is parent of i.
- Root of i is id[id[id[...id[i]...]]].
- Find. Check if p and q have the same root.
- Union. Set the id of q's root to the id of p's root.
- Quick-union defect.
- Trees can get tall.
- Find too expensive (could be N steps)
- Need to do find to do union
Weighted quick-union.
- Modify quick-union to avoid tall trees.
- Keep track of size of each component.
- Balance by linking small tree below large one.
- Implementation.
- Almost identical to quick-union.
- Maintain extra array sz[] to count number of elements in the tree rooted at i.
- Find. Identical to quick-union.
- Union. Modify quick-union to merge smaller tree into larger tree update the sz[] array.
Path compression
- Standard implementation: add second loop to root() to set the id of each examined node to the root.
Simpler one-pass variant: make every other node in path point to its grandparent.
http://www.cnblogs.com/vongang/archive/2011/07/31/2122763.html