9 Aug 2018

Union Find Algorithm

This article focuses on an algorithm for solving problems such as dynamic connectivity, using a data structure called Union Find.

The Evolutionary history of Union Find is From Quick Find –> Union Find –> Weighted Union Find

This is the Performance consumption table:


Dynamic-Connectivity Client

Code:

public static void main(String[] args)
{
    int N = StdIn.readInt();
    UF uf = new UF(N);
    while (!StdIn.isEmpty())
    {
        int p = StdIn.readInt();    
        int q = StdIn.readInt();
        if (!uf.connected(p, q))
        {
            uf.union(p, q);
            StdOut.println(p + " " + q);
        }
    }
}

Quick Find

Code:

public class QuickFindUF
{
    private int[] id;
    private int count;
    public QuickFindUF(int N)
    {
        id = new int[N];
        count =N;
        // Set ID of earch object to itself
        for (int i = 0; i < N; i++)
            id[i] = i;
    }
    
    // check if p and q are in the same component
    public boolean connected(int p, int q)
    { 
        return id[p] == id[q]; 
    }
    
    // find the id for the given index
    public int find(int p)
    {
        return id[p]; 
    }
    
    public int count()
    {
        return count;
    }

    // change all id[p] to id[q]
    public void union(int p, int q)
    {
        int pid = id[p];
        int qid = id[q];
       
        for (int i = 0; i < id.length; i++)
            if (id[i] == pid) id[i] = qid;
        count--;
    }
}

Quick Union

Code:

public class QuickUnionUF
{
    private int[] id;
    private int count;
    public QuickUnionUF(int N)
    {
        id = new int[N];
        count =N;
        // Set ID of earch object to itself
        for (int i = 0; i < N; i++)
            id[i] = i;
    }
    
    // check if p and q have same root
    public boolean connected(int p, int q)
    { 
        return root(p) == root(q); 
    }
    
    // find the id for the given index
    public int find(int i)
    {
        return id[i]; 
    }
    
    public int root(int i)
    {
        //chase parent pointers until reach root
        while(i!=id[i])
        {
            // Make every other node in path point to its grandparent
            id[i] = id[id[i]]; // Pass Compression
            
            i = id[i];
        }
        return i;
    }
    
    public int count()
    {
        return count;
    }
    
    // change all id[p] to id[q]
    public void union(int p, int q)
    {
        int pRoot = root(p);
        int qRoot = root(q);
        
        if(pRoot == qRoot) return;
        id[pRoot] = qRoot; // change root of p to point to root of q
        count--;
    }
}

Weighted Quick Union

Code:

public class WeightedQuickUnionUF
{
    private int[] id;
    private int[] size; // to count number of objs in the each root
    private int count;
    public WeightedQuickUnionUF(int N)
    {
        id = new int[N];
        size = new int[N];
        count = N;
        // Set ID of earch object to itself
        for (int i = 0; i < N; i++)
            id[i] = i;
    }
    
    // check if p and q have same root
    public boolean connected(int p, int q)
    { 
        return root(p) == root(q); 
    }
    
    // find the id for the given index
    public int find(int i)
    {
        return id[i]; 
    }
    
    public int root(int i)
    {
        //chase parent pointers until reach root
        while(i!=id[i])
        {
            // Make every other node in path point to its grandparent
            id[i] = id[id[i]]; // Pass Compression
                        
            i = id[i];
        }
        return i;
    }
    
    public int count()
    {
        return count;
    }
    
    // change all id[p] to id[q]
    public void union(int p, int q)
    {
        int pRoot = root(p);
        int qRoot = root(q);
        
        if(pRoot == qRoot) return;
        
        // Link root of smaller tree to root of larger tree
        if(size[pRoot] < size[qRoot])
        {
            id[qRoot] = pRoot;// change root of q to point to root of p
            size[pRoot] += size[qRoot]; // update the tree size
        }
        else
        {
            id[pRoot] = qRoot;// change root of p to point to root of q
            size[qRoot] += size[pRoot]; // update the tree size
        }
        count--;
    }
}

Comparsion between if it is Weighted or not


End –Cheng Gu


Tags: