Data Structures

Disjoint Set

Introduction

A Disjoint Set data structure keeps track of a set of elements partitioned into a number of disjoint subsets. Disjoint Set supports the following operations:

  • Determine a subset to which a given element belongs. This can be used for determining if two elements are in the same subset.
  • Join two subsets into a one new subset.
  • Create a new subset from the element.
The computational complexity of these operations are near constant. This allows to solve certain problems on Graphs very efficiently. See for example Kruskal's algorithm.

Implementation

C# implementation - Open on Github

This implementation includes the path compression and union by rank optimizations.

Problems

Links

Last updated: 18.12.2020,
created: 23.09.2017.