Dynamic Connectivity Problem

Dynamic Connectivity Problem by Quick-Find and Quick-Union 

Dynamic connectivity Problem is a problem in which we have to find there is a connected path or not for a objects.

Note:-

Only gives there is a path or not.For finding the paths there are other algorithms.

Example:-

There are the following 7 objects.

Union commands on two objects which will join that two objects.

Following union command will apply on these objects:-

union(1,3)

union(2,4)

union(6,7)

union(0,1)

union(5,7)

union(4,5)

And then object connectivity will become:-

Now connected commands would work as:-

connected(0,3)         true

connected(2,7)         true

connected(0,2)         false

Applications involve manipulating objects of all types.

・Pixels in a digital photo.

・Computers in a network.

・Friends in a social network.

・Transistors in a computer chip.

・Elements in a mathematical set.

・Variable names in Fortran program.

・Metallic sites in a composite system.

Now to solve this problem the following two approahes are given below:- 

1.Quick-Find
Quick Find is also known as eager approach.
Union
In this approach,we update value in a array(initialize with no. of objects) with the same value.
Example:-
union(3,4)          Then,    id[3]=id[4]  but now we have to update all the value of objects which are connected to Object 3.
And for all x for id[x]=id[3] update id[x]=id[4]. 

Connected
If id of two objects are equal then they are connected.

Java Program:-

/**

 * @(#)QuickFind2.java

 *

 *

 * @author Suyash Bhala

 * @version 1.00 2015/1/27

 */

/*

 *Quick Find(Eager Approach)

 **/

class UF{

private int id[];

public UF(int N){

id=new int[N];

for(int i=0;i<N;i++){

id[i]=i;

}

}

public boolean connected(int p,int q){

return id[p]==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(pid==id[i]){

id[i]=qid;

}

}

}

}

public class QuickFind2 {

    public static void main(String args[]){

    UF ob=new UF(8);

    ob.union(1,3);

    ob.union(2,4);

    ob.union(6,7);

    ob.union(0,1);

    ob.union(5,7);

    ob.union(4,5);

    System.out.println("Connected(0,3)=>"+ob.connected(0,3));

    System.out.println("Connected(2,7)=>"+ob.connected(2,7));

    System.out.println("Connected(0,2)=>"+ob.connected(0,2));

    }

}

2.Quick-Union
Quick Union is also known as lazy approach.

Union
To connect the objects(let us say union(p,q)) make p child of q by updating id[p]=q.
But for union of child to another root or vice-versa, update id[root(p)]=id[root(q)]

Connected

If root of two objects are equal then they are connected. 

Java Program:-

/**
 * @(#)QuickUnion.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2015/1/28
 */
/*
 *Quick Union(Lazy Approach)
 **/

class UF{
private int id[];
public UF(int N){
id=new int[N];
for(int i=0;i<N;i++){
id[i]=i;
}
}
public boolean connected(int p,int q){
return root(p)==root(q);
}
private int root(int i){
while(i!=id[i]){
i=id[i];
}
return i;
}
public void union(int p,int q){
int i=root(p);
int j=root(q);
id[i]=j;
}
}

public class QuickUnion {

    public static void main(String args[]){
    UF ob=new UF(8);
    ob.union(1,3);
    ob.union(2,4);
    ob.union(6,7);
    ob.union(0,1);
    ob.union(5,7);
    ob.union(4,5);
    System.out.println("Connected(0,3)=>"+ob.connected(0,3));
    System.out.println("Connected(2,7)=>"+ob.connected(2,7));
    System.out.println("Connected(0,2)=>"+ob.connected(0,2));
    }
 

}

Output:-

Connected(0,3)=>true

Connected(2,7)=>true

Connected(0,2)=>false

Analysis:-

Algorithm      initialize      union        find 

Quick-Find          N                 N              1

Quick-Union       N                 N              N

-------------X---------------X--------------X--------------X--------------X-------------