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.

--

--

--

I have a dream to have a spectacular garden

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Building a Climate Dashboard with Apache Pinot and Superset

Selenium 4 — New Features and Enhancements

Giving away free APIs without going broke.

The Eccentric Ways of iOS Safari with the Keyboard

Ease into ML with AWS SageMaker

Setting Instana Running on KIND Cluster

Getting started — GCP’s Cloud run

Capture the Source & Medium using cookies and transfer them with link click

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Ahmad Berahman

Ahmad Berahman

I have a dream to have a spectacular garden

More from Medium

Time Conversion | HackerRank Problem | Java Solution

Let’s dive into head first Java

Let’s talk about head first Java

How to begin with JAVA