Quick Find is an eager union-find algorithm.
Purpose: To find if two elements are connected and to perform union operation on two elements.
We will consider the elements as simple int array. We initialize array to index elements itself and then change the ids in the array when an union operation is performed.
Array accesses: 2N+1
initialize - N
union(p,q) - N
connected(p,q) - 1
If N unions are performed on N elements, union takes N2 array access. Quadratic operations don't scale.
Following is the program:
Purpose: To find if two elements are connected and to perform union operation on two elements.
We will consider the elements as simple int array. We initialize array to index elements itself and then change the ids in the array when an union operation is performed.
Array accesses: 2N+1
initialize - N
union(p,q) - N
connected(p,q) - 1
If N unions are performed on N elements, union takes N2 array access. Quadratic operations don't scale.
Following is the program:
No comments:
Post a Comment