Finding the shortest path between a pair of vertices.
Two sub-problems:
find(p, q)checks for connectivity between two verticesunion(p, q)connects two vertices
| Algorithm | find | union | Limitation |
|---|---|---|---|
| Quick-Find | Slow when union is expensive, tree is flat | ||
| Quick-Union | Slow when trees too tall, union and find both expensive | ||
| Weighted Union | |||
| Weighted Union with Path Compression | Almost linear performance per operation. Trees are effectively flat |