Skip to content

A union-find disjoint sets data structure implemented in Python with the "Weighted Quick Union with Path Compression" algorithm.

License

Notifications You must be signed in to change notification settings

deehzee/unionfind

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

8 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

UnionFind Implementation in Python

Union-find is a data structure that maintains disjoint set (called connected components or components in short) membership, and makes it easier to merge (union) two components, and to find if two elements are connected (i.e., belong to the same component).

This implements the "weighted-quick-union-with-path-compression" union-find algorithm. Only works if elements are immutable objects.

Worst case for union and find (N + M \log^* N), with N elements and M union/find operations. The function \log^* is the number of times needed to take \log (base 2) of a number until reaching 1. In practice, the amortized cost of each operation is nearly linear [1].

Update: This has now been packaged into an instalable pip package by Hagai Helman Tov (@hagai-helman). See the fork at https://github.com/hagai-helman/unionfind).

Contents

  • Module unionfind with the class UnionFind
  • An example notebook UnionFindExamples.ipynb
  • License: MIT.

Requirements

  • numpy
[1]http://algs4.cs.princeton.edu/lectures/

About

A union-find disjoint sets data structure implemented in Python with the "Weighted Quick Union with Path Compression" algorithm.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published