# Question: Dynamic Connectivity

Q: Given two points, are there any path connecting them? We also connect points dynamically.

## Modeling

• Reflexive: p is connected to p
• Symmetric: if p is connected to q, then q is connected to p
• Transitive: if p is connected to q and q is connected to r, then p is connected to r.
• Connected components: Given points, we can create connected componenets. Then we should deal with the question: Is P and Q connected?

e.x: {0} {1,2,3} {4,5}: in each set points and muturally connected. If we connect 2 and 5, we can achieve a c.c: {0} {1,2,3,4,5}

# Anwser 1: Quick find

• For {0} {1,2,3}, we give them different Component ID: 0, 1. So 0 has a CID of 0. 1,2, and 3 have a CID of 1.

• When we need to figure out whether two points and connected. We can check if they have the same CID.

• Futher more, we can decided the CID just by the one of point number in the component since neither two of their numbers equals.

• Data structure:

Array: `[id] = groupID`

The ID represents each number of the point and value represents CID.

e.x. For {0} {1,2,3} {4,5} we have:

``````       0  1  2  3  4  5
id[]   0  2  2  2  5  5
``````

There are 3 different components.

## Code

``````public class QuickFindUF
{
private int[] id;
// init
public QuickFindUF(int N)
{
id = new int[N];
for (int i = 0; i < N; i++)
{
id[i] = i;
}
}
public boolean connected(int p, int q)
{  return id[p] == id[q];  }
public void union(int p, int q)
{
int pid = id[p];
int qid = id[q];
for (int i = 0; i < id.length; i++)
if (id[i] == pid) id[i] = qid;
}
}
``````

## Cost

### Union

N: Each call of `union()` need at most N times of comparing and changing.

For N points, its cost’s N^2.

### Find

`1`: Checking two value only.

### Initiallize

`N`: Each one has to been given a value.

### Summary

We can’t accept quadratic time algorithms for large problems. The reason is they don’t scale. As computers get faster and bigger, quadratic algorithms actually get slower.

This algorithm can find quickly, so we call it Quick Find. But its unioning speed is too slow.

Treat these point as trees(forest):

e.x. {0} {1} {2,3,4,9} {5,6} {7} {8} -> ## Data Structure

Array: `[id] = itsParent`

## Algorithm

Operation `union()` is faster by:

For each `union()`, treat the first element as child, and the other as parent.

e.x. union(9,6): In this case, we only need to change one value whatever the situation.

## Code

``````public class QuickUnionUF
{
private int[] id;
// init
public QuickUnionUF(int N)
{
id = new int[N];
for (int i = 0; i < N; i++) id[i] = i;
}
private int root(int i)
{
while (i != id[i]) i = id[i];
return i;
}
public boolean connected(int p, int q)
{
return root(p) == root(q);
}
public void union(int p, int q)
{
int i = root(p);
int j = root(q);
id[i] = j;
}
}
``````

## Cost ### Connected

N: for each point, one call for root costs at most N times(include cost of root equals root comparison). So it’s 2N. ->N.

### Union

N: each `union()` operation call for root costs at most N times(include cost of root equals root comparison). So it’s 2N. ->N.

### Summary

#### Quick-find defect

• Union too expensive (N array-accesses).
• Trees are flat, but too expensive to keep them flat.

#### Quick-union defect

• Trees can get tall.
• Find too expensive (could be N array accesses).

Modify quick-union to avoid tall trees. Balance by linking root of smaller tree to root of larger tree. So we can get a lower depth of tree. ## How to ensure each node has a lower depth?

While unioning two trees, we just let the smaller(by numbers of size) one to below the bigger one.

e.x. after union(7,3) ## Why this works?

• For each `union()` , the smaller tree get 1 depth increase, and larger one get nothing change. So the deepest tree of all maybe increase by 1.(assume that there are two deepest trees share the same depth)

• For each `union()` , the nodes of the smaller tree will at lease double, since the larger tree has no nodes less than that.

• Let’s assume that these nodes will be unioned into one singal tree to make the tree as deep and large as possible.

• Pick one random tree for example, T. For each `union()` , it may increase 1 depth or not. If it increase every time(the extreme situation), its nodes will double(at least) every time. T can double at most lg(log2) N times. Because:

`2^(lg N) = N`

After double lg N times, its number of node will increase to N, the total number of nodes.

• As a result, even if T adds depth every time `union()` , depth of T is at most lg N.

`lg x = log(2,x)`

## Cost ### Initialize

N: id[] + sz[] = 2N -> N.

### Union(each)

lg N: T(root()) = lg N

### Connectted

lg N: T(root()) = lg N

# Other improvements

## Path compression For every node call root(), it will make this node connect directly to root.

## Summary 