Weighted Quick-Union, “Algorithms” by Sedgewick & Wayne, page 228

Here is the Java source code for a version of the Weighted Quick-Union algorithm that will automatically read-in the tinyUF.txt “connections” text file, from your local drive, provided by the authors (which you can find here). Unlike the source code in the book, which requires that you manually type in all the integer values yourself (contained in the txt file), this one does that work for you.

Here is the code, enjoy::::::::::::::

import java.io.File;
import java.util.Scanner;

public class WeightedQuickUnion {
private int[] id; // parent link (site indexed)
private int[] sz; // sz of group for roots (site indexed)
private int count; // number of components
private int N;

public WeightedQuickUnion(int N){
this.N = N;
count = N;

id = new int[N];
for (int i = 0; i < N; i++){
id[i] = i;
}

sz = new int[N];
for (int i = 0; i < N; i++){
sz[i] = 1; // for each site set the number of nodes on the tree
}

System.out.print(“Current array status: “);
for (int a = 0; a < N; a++){
System.out.print(id[a]);
}
System.out.println(“”);
}//end WeghtedQuickUnion constructor

public int count(){
return count;
}//end count()

public boolean connected(int p, int q){
return find(p) == find(q); //are the roots of p and q equal?
}//end connected()

public int find(int p){
while (p != id[p]){//find the root of p
p = id[p];
}
return p;
}//end find()

public void union(int p, int q){//
int i = find(p);
int j = find(q);

if (i == j) {
return;
}
//make smaller root point to larger root
System.out.print(“The size of ” + p + “‘s group is : ” + sz[i]);
System.out.println(“. The size ” + q + “‘s group is : ” + sz[j]);
if (sz[i] < sz[j]){//if the size of p’s group is less than q’s group
id[i] = j;//set the root of p to the root of q
sz[j] += sz[i];//add p’s group members to q’s group
} else {
id[j] = i;//set the root of q to the root of p
sz[i] += sz[j];
}
count–;//decrement, 2 minus signs

System.out.println(p + ” and ” + q + ” are now connected”);
System.out.print(“The root of ” + p + ” is: ” + id[p]);
System.out.println(“. The root of ” + q + ” is: ” + id[q]);
System.out.print(“Current array status: “);
for (int a = 0; a < N; a++){
System.out.print(id[a]);
}
System.out.println(“”);
}//end union()

public static void main(String[] args) {
Scanner scan = null;
try{
scan = new Scanner(new File(//use foreword slashes next
“C:/whereever you saved the txt file/tinyUF.txt”));
} catch (Exception ex){
System.out.println(“Could not find file”);
}
int N = scan.nextInt();// read number of id.
System.out.println(“Array length is: ” + N);

WeightedQuickUnion wqu = new WeightedQuickUnion(N);
while (scan.hasNext()){
int p = scan.nextInt();
int q = scan.nextInt(); //read pair to connect
if (wqu.connected(p, q)){
System.out.println(p + ” and ” + q + ” are already connected”);
continue; //ignore if connected
}
wqu.union(p, q); //combine components

}
StdOut.println(wqu.count() + ” components”);
scan.close();
}//end main()
}

||||||||||||||END OF SOURCE CODE|||||||||||

This is what the tinyUF trees look like after the 11 connections:

And this is the printout you should get in the command line or Console of your IDE:

Array length is: 10
Current array status: 0123456789
The size of 4’s group is : 1. The size 3’s group is : 1
4 and 3 are now connected
The root of 4 is: 4. The root of 3 is: 4
Current array status: 0124456789
The size of 3’s group is : 2. The size 8’s group is : 1
3 and 8 are now connected
The root of 3 is: 4. The root of 8 is: 4
Current array status: 0124456749
The size of 6’s group is : 1. The size 5’s group is : 1
6 and 5 are now connected
The root of 6 is: 6. The root of 5 is: 6
Current array status: 0124466749
The size of 9’s group is : 1. The size 4’s group is : 3
9 and 4 are now connected
The root of 9 is: 4. The root of 4 is: 4
Current array status: 0124466744
The size of 2’s group is : 1. The size 1’s group is : 1
2 and 1 are now connected
The root of 2 is: 2. The root of 1 is: 2
Current array status: 0224466744
8 and 9 are already connected
The size of 5’s group is : 2. The size 0’s group is : 1
5 and 0 are now connected
The root of 5 is: 6. The root of 0 is: 6
Current array status: 6224466744
The size of 7’s group is : 1. The size 2’s group is : 2
7 and 2 are now connected
The root of 7 is: 2. The root of 2 is: 2
Current array status: 6224466244
The size of 6’s group is : 3. The size 1’s group is : 3
6 and 1 are now connected
The root of 6 is: 6. The root of 1 is: 2
Current array status: 6264466244
1 and 0 are already connected
6 and 7 are already connected
2 components

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s