Dynamic Connectivity

The problem statement is, it is given us a set of objects and we are asked if there is a path connecting the two objects , there is no need to connect two objects and if there is no path between two objects, so connect two objects.

What is Dynamic Connectivity?
According to Wikipedia, a dynamic connectivity structure is a data structure that dynamically maintains information about the connected components of a graph.

To solve the dynamic connectivity problem we use set of algorithms which names is Union find that it contains two classical algorithms Quick-Find and Quick-Union but actually I want to use efficient data structure so I use WQUPC theory that in practice is Linear.

Defects of Quick-Find are :

1. Union too expensive
2. Tree are flat, but too expensive to keep them flat

Defects of Quick-Union are :

1. Trees can get tall
2. Find too expensive

So We need two improvement approach :

Wighting and Path Compression

To solve this problem we need 2 critical methods which names is Union and isConnected. In Union method, we connect 2 objects to each other and in isConnected method, we check whether there is any path between 2 objects or no ?

Same as Quick-Find and Quick-Union algorithms ,i have Integer array of length N and set id of each objects to itself but maintain extra array size to count number of objects in the tree rooted to control Weighting of tree.

Root method with Path Compression approach(just after computing the root of p,set the id of each examined node to point to that root) that doing chase parent pointers until reach root

isConnected method that check, are p and q in the same component?

And Union method with Weighting approach(modify Quick-Union to avoid tall tree, so keep track of size of each tree and balance by linking root of smaller tree to root of larger tree) that adding connection between p and q .

To access to completed source, please check Room Project on this link.

Resources : Algorithms Robert Sedgewick