Algorithms - Dynamic connectivity problem

DYNAMIC CONNECTIVITY PROBLEM –

Is ‘0’ connected to ‘2’.  YES

Is ‘2’ connected to ‘3’. NO

The algorithm will give you answer in YES or NO. It will not give you the path from src to dest.

Connected components are –    {10},                       {0, 1, 2, 4, 5, 6},                  {3, 7, 8, 9}

Two basic operation-

·         Union command – Joins two nodes ONLY if they are not connected (DIRECTLY or INDIRECTLY).

·         Find query – Answers in YES or NO, if two nodes are connected directly or indirectly.

Couple of approaches in implementing

1)      Quick Find – (BAD) as ‘union’ operation goes in O(n²).

2)      Quick union – (GOOD) as it works in logarithmic times.

a.       Improvement  1. Keep it balanced by using an auxiliary array. In Weighed quick union, we make the root of the smaller tree (IN TERMS OF NUMBER OF NODES, NOT HEIGHT), the root of the larger tree.

b.      Improvement 2 – path compression.

One of the practical usage of solving this problem is MONTE CARLO SIMULATIONS.

Monte Carlo simulations can be used to find the percolation threshold.

The system will percolate if there is a connectivity between top and bottom. Each site is open with a probability p.

This can only be found using COMPUTATIONAL MODELS rather than MATHMATICAL MODELS.

With random tries of various values for n in the grid above and multiple experiments, it is found that at p=0.592746, the system percolates.