The basic premise of the Dynamic Connectivity problem.

0-dynamic-connectivity-setup.md

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton).

##The Problem

Say we have have some points, which we decide to store in an array.
Say we number these points so that we can tell them apart.

What we have is something like this:

point array: [1][2][3][4] ... [N]

Now lets imagine that these some of these points are interconnected somehow:
2 could be linked to 10, 40 could be linked to 2031, and so on.

It is possible that these connections could form paths:
2 is linked to 10, which is linked to 405, which is linked to 40, which is linked to 2031.
In such a case, 2 would essentially be linked to 2031 - along with 10, 405 and 40.

Now if we had a lot of points (N is big) and a lot of connections between these points, there are two main questions which are interesting to ask:

1. "How could we know if two points are connected?" and

2. "If the situation changed, how quickly could we re-connect and change the paths between points?"

These two questions are what generally define the Dynamic Connectivity Problem.

##Setup

In general, algorithms tackling with the Dynamic Connectivity Problem deal with 2 arrays:

The first is the actual array of points from [1] to [N], which doesn't change.

The second is an array that Princeton names the "id-array" which represents relationships between the points.

• Each item in the point array has a corresponding item in the id-array.
• The id array shows what its corresponding point is connected to.

####Example: point array [1] [2] [3] [4] [5] id array [2] [4] [3] [4] [2]

[1] is connected to [2]
[2] is connected to [4]
[3] is connected to itself (it has no connection)
and so on...

Graphically, the id-array tells us would look like this:

  4    3
  |
  2
 / \
5   1

Full interconnected shapes are called "trees" or "connected components".
Individual paths within trees are called "branches". The numbers at the top (those connected to themselves) are termed "roots".

There are a few useful thoughts that we can take from this:

• All numbers within a tree have the same root.
  Because of the way we have defined the connections, trees can only ever have one root.
  In the above example, point [2] can only has one corresponding item in the id-array, and so cannot be connected to both point [4] and point [3].
• All points within a tree are connected.
• Because of the above two thoughts, we can say that all points that have the same root are connected.