Skip to content
This repository has been archived by the owner on May 18, 2020. It is now read-only.

Latest commit

 

History

History
86 lines (55 loc) · 3.52 KB

README.md

File metadata and controls

86 lines (55 loc) · 3.52 KB

Dynamic Connectivity

Dynamic Connectivity is a data structure that dynamically maintains information about the connected components of a graph.

Requirements & Assumptions

Given a set of N objects, the algorithm must

  • connect two objects (union opertation)
  • determine if there is a path connecting two objects (find/connected query)

Assume "is connected to" is an equivalance relation.

Propery Description
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

Typical applications include

  • Computers in a network
  • Friends in a social network
  • Transistors in a computer chip

Implementation

Quick-find (Eager Approach)

Given two items p and q

  • change all entries with id[p] to id[q] to perform a union operation
  • are connected if id[p] == id[q]

UF Class

Operation Description Complexity
UF(int N) Initialize union-find data structure with N objects N
void union(int p, int q) Add connections between p and q N
boolean connected(int p, int q) Check id[p] and id[q] have same values 1

Quick-find union is too expensive! Takes N2 array accesses to process sequence of N union commands on N objects.

For 109 objects, it would take 109 union commands. Hence it would take 1018 operations or over 30 years for the fastest computer on this planet to complete the computation.

Quick-union (Lazy Approach)

Given two items p and q

  • take the root of the component containing the first item and make that child of the root of the component containing the second item (Union Operation)

QuickUnionUF Class

Operation Description Complexity
QuickUnionUF(int N) Initialize Quick-union data structure with N objects N
void union(int p, int q) Change root of p to point to root of q N (Worst Case)
boolean connected(int p, int q) Check p and q have same root N (Worst Case)

Quick-union is also too slow for cases when the tree get's really tall (Worst Case). Operation to find the root of the item is too expensive and could potentially require N array accesses.

Weighted Quick-union with Path Compression (Optimal Approach)

Given two items p and q

  • keep track of number of objects in each tree and maintain balance by ensuring we link the root of the smaller tree to the root of the larger tree (i.e. guarentees that no item is not too far from the root)

WeightedUnionUF Class

Operation Description Complexity
WeightedQuickUnionUF(int N) Initialize Weighted Quick-union data structure with N objects N
void union(int p, int q) Change root of p to point to root of q lg N
boolean connected(int p, int q) Check p and q have same root lg N

Quick Union-find with compression is the ideal approach. For 109 unions/finds for 109 objects, Weighted Quick-union with compression reduces time to 6 seconds from 30 years required for the Quick-find.