Problem Detail: I know that the disjoint set datastructure is used to keep track of the connected components of an undirected graph when the edges are added to the graph dynamically . I also know that is is used in Kruskal’s algorithm for minimum spanning trees . What are the other possible applications of this datastructure ?
Asked By : Geek
Answered By : Realz Slaw
- Maze generation (using a modified Kruskal’s algorithm)
- Tarjan’s off-line least common ancestors algorithm
- Connected component labeling
- Online maintenance of biconnected components
- Validation Hindley–Milner rules
- Computing the winner of Havannah board game (see Efficient Playouts for the Havannah Abstract Board Game)
- Alias analysis
- Used in construction of contour trees (see Laying the Foundations for an Advanced Visualization System in O’Caml and Multi-Resolution computation and presentation of Contour Trees)
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6308
