Given a disjoint set data structure, I use two strategies - union by rank and path compression - to find the connected components of the structure's graph.
Table of Contents
A graph is a data structure composed of vertices connected by edges.
A graph can consist of one or more connected components: these are sets of vertices that are connected by edges. The picture above shows a graph with three connected components.
Here is an algorithm to find all of the connected components in a graph:
- Make a set for each vertex in the graph, with the label of that vertex being the sole element of the set.
- For each edge in the set:
- Check to see if the vertices at either end of the edge lie in different sets.
- If they do, replace the two separate sets with a single set that is the union of the two separate sets.
- Once all of the edges has been processed, output the list of sets that remain. These are the connected components of the graph.
Here is a picture that illustrates how this algorithm works.
The objective of this program is to use the methods, union by rank and path compression, to create an algorithm that can efficiently connect components of such a graph.
To get a local copy up and running follow these simple steps.
Things you need to use the software.
- MacOS
- Xcode
Clone this repo.
git clone https://github.com/vmthanh-bi/Union-by-rank-Path-compression.gitSee the open issues for a list of proposed features (and known issues).
Tony Vu - @vmthanh.bi - vmthanh.bi@gmail.com
Project Link: https://github.com/vmthanh-bi/Union-by-rank-Path-compression