1. Union-Find

Question 1

We assume in Dynamic connectivity that “is connected to” is an equivalence relation:
transitive:

Answer 1

If p is connected to q and q is connected to r, then p is connected to r

Question 1

We assume in Dynamic connectivity that “is connected to” is an equivalence relation:
symmetric:

Answer 1

If p is connected to q, then q is connected to p.

Question 2

We assume in Dynamic connectivity that “is connected to” is an equivalence relation:
reflexive:

Answer 2

p is connected to p.

Question 3

An equivalence relation partitions the objects into

Answer 3

equivalence classes or connected components.

Question 4

Quick-find

Answer 4

maintains the invariant that p and q are connected if and only if id[p] is equal to id[q]. In other words, all sites in a component must have the same value in id[].

Question 5

//QuickFindUF.java
public class QuickFindUF {

Answer 5

private int[] id; // id[i] = component identifier of i
private int count; // number of components
public QuickFindUF(int n) {
count = n;
id = new int[n];
for (int i = 0; i < n; i++)
id[i] = i;
}

Question 6

//QuickFindUF.java
/**
* Returns the number of sets
*/

Answer 6

public int count() {
return count;
}

Question 7

//QuickFindUF.java
/**
* Returns the canonical element of the set containing element {@code p}.
*/

Answer 7

public int find(int p) {
validate(p);
return id[p];
}

Question 8

//QuickFindUF.java

// validate that p is a valid index

Answer 8

private void validate(int p) {
int n = id.length;
if (p < 0 || p >= n) {
throw new IllegalArgumentException(“index “ + p + “ is not between 0 and “ + (n-1));
}
}

Question 9

//QuickFindUF.java
/**
* Returns true if the two elements are in the same set.
*/

Answer 9

public boolean connected(int p, int q) {
validate(p);
validate(q);
return id[p] == id[q];
}

Question 10

//QuickFindUF.java

/**
* Merges the set containing element
*/

Answer 10

public void union(int p, int q) {
validate(p);
validate(q);
int pID = id[p]; // needed for correctness
int qID = id[q]; // to reduce the number of array accesses

    // p and q are already in the same component
    if (pID == qID) return;

    for (int i = 0; i < id.length; i++)
        if (id[i] == pID) id[i] = qID;
    count--;
}

Question 11

//QuickFindUF.java

/**
* Reads an integer {@code n} and a sequence of pairs of integers
* (between {@code 0} and {@code n-1}) from standard input, where each integer
* in the pair represents some element;
* if the elements are in different sets, merge the two sets
* and print the pair to standard output.

*/

Answer 11

public static void main(String[] args) {
int n = StdIn.readInt();
QuickFindUF uf = new QuickFindUF(n);
while (!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();
if (uf.find(p) == uf.find(q)) continue;
uf.union(p, q);
StdOut.println(p + “ “ + q);
}
StdOut.println(uf.count() + “ components”);
}

}

Question 12

Quick-union

Answer 12

is based on the same data structure—the site-indexed id[] array—but it uses a different interpretation of the values that leads to more complicated structures. Specifically, the id[] entry for each site will be the name of another site in the same component (possibly itself). To implement find() we start at the given site, follow its link to another site, follow that sites link to yet another site, and so forth, following links until reaching a root, a site that has a link to itself. Two sites are in the same component if and only if this process leads them to the same root. To validate this process, we need union() to maintain this invariant, which is easily arranged: we follow links to find the roots associated with each of the given sites, then rename one of the components by linking one of these roots to the other.

Question 13

//QuickUnionUF.java

Answer 13

public class QuickUnionUF {
private int[] parent; // parent[i] = parent of i
private int count; // number of components

/**
 * Initializes an empty union-find data structure with
 */
public QuickUnionUF(int n) {
    parent = new int[n];
    count = n;
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
}

Question 14

//QuickUnionUF.java

/**
* Returns the number of sets.
*/

Answer 14

public int count() {
return count;
}

Question 15

//QuickUnionUF.java

/**
* Returns the canonical element of the set containing element {@code p}.
*/

Answer 15

public int find(int p) {
validate(p);
while (p != parent[p])
p = parent[p];
return p;
}

Question 16

//QuickUnionUF.java

// validate that p is a valid index

Answer 16

private void validate(int p) {
int n = parent.length;
if (p < 0 || p >= n) {
throw new IllegalArgumentException(“index “ + p + “ is not between 0 and “ + (n-1));
}
}

Question 17

//QuickUnionUF.java
/**
* Returns true if the two elements are in the same set.
*/
@Deprecated

Answer 17

public boolean connected(int p, int q) {
return find(p) == find(q);
}

Question 18

//QuickUnionUF.java

/**
* Merges the set containing element */
public void union(int p, int q) {

Answer 18

int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
parent[rootP] = rootQ;
count–;
}

Question 19

//QuickUnionUF.java
/**
* Reads an integer {@code n} and a sequence of pairs of integers
*/
public static void main(String[] args) {

Answer 19

QuickUnionUF uf = new QuickUnionUF(n);
while (!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();
if (uf.find(p) == uf.find(q)) continue;
uf.union(p, q);
StdOut.println(p + “ “ + q);
}
StdOut.println(uf.count() + “ components”);
}

}

Question 20

Weighted quick-union.

Answer 20

Rather than arbitrarily connecting the second tree to the first for union() in the quick-union algorithm, we keep track of the size of each tree and always connect the smaller tree to the larger

Question 21

//WeightedQuickUnionUF.java

public class WeightedQuickUnionUF {

Answer 21

private int[] parent; // parent[i] = parent of i
private int[] size; // size[i] = number of elements in subtree rooted at i
private int count; // number of components

/**
 * Initializes an empty union-find data structure with
  */
public WeightedQuickUnionUF(int n) {
    count = n;
    parent = new int[n];
    size = new int[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        size[i] = 1;
    }
}

Question 22

//WeightedQuickUnionUF.java
/**
* Returns the number of sets.
*
*/
public int count() {

Answer 22

return count;
}

Question 23

//WeightedQuickUnionUF.java
/**
* Returns the canonical element of the set containing element {@code p}.
*/
public int find(int p) {

Answer 23

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

Question 24

//WeightedQuickUnionUF.java
/**
* Returns true if the two elements are in the same set.
*/
public boolean connected(int p, int q) {

Answer 24

return find(p) == find(q);
}

Question 25

//WeightedQuickUnionUF.java
// validate that p is a valid index
private void validate(int p) {

Answer 25

int n = parent.length;
if (p < 0 || p >= n) {
throw new IllegalArgumentException(“index “ + p + “ is not between 0 and “ + (n-1));
}
}

Question 26

//WeightedQuickUnionUF.java
/**
* Merges the set containing element {@code p} with the set
*/
public void union(int p, int q) {

Answer 26

int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;

    // make smaller root point to larger one
    if (size[rootP] < size[rootQ]) {
        parent[rootP] = rootQ;
        size[rootQ] += size[rootP];
    }
    else {
        parent[rootQ] = rootP;
        size[rootP] += size[rootQ];
    }
    count--;
}

Question 27

//WeightedQuickUnionUF.java
/**
* Reads an integer {@code n} and a sequence of pairs of integers
* (between {@code 0} and {@code n-1}) from standard input, where each integer
* in the pair represents some element;
* if the elements are in different sets, merge the two sets
* and print the pair to standard output.
*
*/
public static void main(String[] args) {

Answer 27

int n = StdIn.readInt();
WeightedQuickUnionUF uf = new WeightedQuickUnionUF(n);
while (!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();
if (uf.find(p) == uf.find(q)) continue;
uf.union(p, q);
StdOut.println(p + “ “ + q);
}
StdOut.println(uf.count() + “ components”);
}

}

Question 28

Weighted quick-union with path compression.

Answer 28

There are a number of easy ways to improve the weighted quick-union algorithm further. Ideally, we would like every node to link directly to the root of its tree, but we do not want to pay the price of changing a large number of links. We can approach the ideal simply by making all the nodes that we do examine directly link to the root.

Question 29

Union-find cost model.

Answer 29

When studying algorithms for union-find, we count the number of array accesses (number of times an array entry is accessed, for read or write).

Question 30

Definitions

Answer 30

The size of a tree is its number of nodes.
The depth of a node in a tree is the number of links on the path from it to the root.
The height of a tree is the maximum depth among its nodes.

Question 31

Proposition

Answer 31

The quick-find algorithm uses one array access for each call to find() and between n + 3 and 2n + 1 array accesses for each call to union() that combines two components.
The number of array accesses used by find() in quick-union is 1 plus twice the depth of the node corresponding to the given site.
The number of array accesses used by union() and connected() is the cost of the two find() operations (plus 1 for union() if the given sites are in different trees).
The depth of any node in a forest built by weighted quick-union for n sites is at most lg n.

Question 32

Corollary

Answer 32

For weighted quick-union with n sites, the worst-case order of growth of the cost of find(), connected(), and union() is log n.

Question 33

Is there an efficient data structure that supports both insertion and deletion of edges?

Answer 33

Yes. However, the best-known fully dynamic data structure for graph connectivity is substantially more complicated than the incremental version we consider. Moreover, it’s not as efficient. See Near-optimal fully-dynamic graph connectivity by Mikkel Thorup.