Sitemap
OmarElgabry's Blog

This is my freedom area. Don't underestimate it. The devil is in the detail.

Follow publication

Dynamic Connectivity Problem

7 min readJan 5, 2017

--

Connected Objects

Given a set of N objects, connect two objects, or ask if two objects are connected (directly or in-directly).

union(2, 5)        // connect object 2 with object 5
connected(1 , 6) // is object 1 connected to object 6?

Connection Properties

Implementing The Operations

Union-Find — algs4.cs.princeton.edu

Union-Find Data Type

Quick Find

Initialize

for (int i = 0; i < n; i++)
id[i] = i; // set id of the object at index i

Union

if (pID == qID) return;   // already connected?for (int i = 0; i < id.length; i++)
if (id[i] == pID)
id[i] = qID;
Quick Find

Connected

return id[p] == id[q];

Analyzing

Quick Union

Initialize

for (int i = 0; i < n; i++)
parent[i] = i; // set parent of the object at index i

Root

while (p != parent[p])
p = parent[p];
return p;

Union

int rootP = root(p);
int rootQ = root(q);
if (rootP == rootQ) return; // already connected?
parent[rootP] = rootQ;
Quick Union

Connected

return root(p) == root(q);

Analyzing

Quick Union Improvements

1. Weighted Quick Union

Weighted Quick Union— algs4.cs.princeton.edu
// union by size (initially size[i] = 1)
if (size[rootP] < size[rootQ]) {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
}
// union by depth (initially depth[i] = 0)
if (depth[rootP] < depth[rootQ])
parent[rootP] = rootQ;
else if (depth[rootP] > depth[rootQ])
parent[rootQ] = rootP;
else {
parent[rootQ] = rootP;
depth[rootP]++;
}

Analyzing

2. Path Compression

Path Compression — algs4.cs.princeton.edu
// path compression by linking to the root
int root = p;
while (root != parent[root])
root = parent[root];
while (p != root) {
int newp = parent[p];
parent[p] = root;
p = newp;
}
// path compression by linking to grandparent(halving the depth)
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}

Analyzing

Summary

Other Related Problems (Percolation)

Percolation — introcs.cs.princeton.edu
Percolation — introcs.cs.princeton.edu

Watch out for this bug!

Percolation — introcs.cs.princeton.edu

Solutions

--

--

OmarElgabry's Blog
OmarElgabry's Blog

Published in OmarElgabry's Blog

This is my freedom area. Don't underestimate it. The devil is in the detail.

Omar Elgabry
Omar Elgabry

Written by Omar Elgabry

Software Engineer. Going to the moon 🌑. When I die, turn my blog into a story. @https://www.linkedin.com/in/omarelgabry