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