1 - Union-Find

1. Dynamic Connectivity

  • Given a set of N objects.
    • Union command: connect two objects.
    • Find/connected query: is there a path connecting the two objects?
  • We assume "is connected to" is an equivalence relation:
    • 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. Maximal set of objects that are mutually connected.

1.1. Implementation

  • The method called Weighted quick-union with path compression.
  • quick-union:
  • weighted: Keep track of size of each tree (number of objects). Balance by linking root of smaller tree to root of larger tree.
    • Keep the depth of any node x is at most lg N.
  • path compression: Make every other node in path point to its grandparent.
  • Code:

      package week1;
    
      import common.StdIn;
    
      import java.io.FileNotFoundException;
      import java.util.Scanner;
    
      public class UnionFind {
    
        private int count;
        private int[] parent;
        private int[] sz; // record the weight
    
        UnionFind(int n) {
          count = n;
          parent = new int[n];
          sz = new int[n];
          for(int i=0; i<n; i++) {
            parent[i] = i;
            sz[i] = 1;
          }
        }
    
        public int root(int id) {
          while (parent[id] != id) {
            parent[id] = parent[parent[id]]; // improve
            id = parent[id];
          }
          return id;
        }
    
        public boolean connected(int p, int q) {
          return root(p) == root(q);
        }
    
        // quick union
        public void union(int p, int q) {
          int rootP = root(p);
          int rootQ = root(q);
          if(sz[rootP] <= sz[rootQ]) {
            parent[rootP] = rootQ;
            sz[rootQ] += sz[rootP];
          } else {
            parent[rootQ] = rootP;
            sz[rootP] += sz[rootQ];
          }
          count --;
        }
    
        public int count() {
          return count;
        }
    
        public static void main(String[] args) {
          Scanner sc = null;
          try {
            sc = new Scanner(StdIn.getDataFile("mediumUF.txt"));
          } catch (FileNotFoundException e) {
            e.printStackTrace();
          }
          int n = sc.nextInt();
          UnionFind uf = new UnionFind(n);
          while (sc.hasNext()) {
            int p = sc.nextInt();
            int q = sc.nextInt();
            if (uf.connected(p, q)) continue;
            uf.union(p, q);
            System.out.println(p + " " + q);
          }
          System.out.println(uf.count() + " components");
        }
      }
    

    2. Assignment (Percolation)

  • Write a program to estimate the value of the percolation threshold via Monte Carlo simulation.

  • My Code: https://github.com/erictt/computer-science-learning/tree/master/algorithms-1/programming/src/week1/assignment

results matching ""

    No results matching ""