CSC212 Union Find in Java

--D. Thiebaut (talk) 10:58, 25 November 2014 (EST)

---

Version 1

Source

public class UnionFind {
	static int[] id = null;
	static int noVertices = 0;
	
	public static void initQuickFind( int n ) {
		noVertices = n;
		id = new int[noVertices];		
		for ( int i=0; i<noVertices; i++ )
			id[i] = i;			
	}
	
	/**
	 * return Id of Vertex p (does not modify p)
	 * @param p: id of vertex we're interested in.
	 * @return Id of p
	 */
	public static int idOf( int p ) {
		while ( id[ p ] != p ) p = id[ p ];
		return p;
	}
	
	public static boolean quickFind( int p, int q ) {
		return idOf( p ) == idOf( q );
	}
	
	public static void quickUnite( int p, int q ) {
		int id_p = idOf( p );
		int id_q = idOf( q );
		if ( id_p == id_q ) return;
		id[ id_p ] = id_q;
	}
	
	public static void displayQF( String caption ) {
		System.out.println( "\nId array " + caption );
		for ( int i=0; i<noVertices; i++ )
			System.out.print( String.format( "%3d ", i ) );
		System.out.println();
		for ( int i=0; i<noVertices; i++ )
			System.out.print( String.format( "%3d ", id[i] ) );
		System.out.println();		
	}
	
	public static void displayIds( ) {
		for ( int i=0; i<noVertices; i++ )
			System.out.println( "Id of " + i + " = " + idOf( i ) );
	}
	
	public static void main(String[] args) {
		initQuickFind( 10 );
		
		quickUnite( 3, 5 );
		displayQF( "after adding 3-5" );

		quickUnite( 4, 6 );
		displayQF( "after adding 4-6" );

		quickUnite( 4, 3 );
		displayQF( "after adding 4-3" );
		
		quickUnite( 7, 8 );
		quickUnite( 9, 8 );
		displayQF( "after adding 7-8, 9-8" );
		
		quickUnite( 7, 3 );
		displayQF( "after adding 7-3" );
		displayIds();
	}

}

Output

after adding 3-5
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   3   4   3   6   7   8   9 
Size  :   1   1   1   1   1   2   1   1   1   1 

after adding 4-6
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   3   4   3   4   7   8   9 
Size  :   1   1   1   1   1   2   2   1   1   1 

after adding 4-3
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   4   4   3   4   7   8   9 
Size  :   1   1   1   2   1   2   2   1   1   1 

after adding 7-8, 9-8
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   4   4   3   4   9   7   9 
Size  :   1   1   1   2   1   2   2   2   2   1 

after adding 7-3
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   4   9   3   4   9   7   9 
Size  :   1   1   1   2   2   2   2   2   2   1 

Id of 0 = 0
Id of 1 = 1
Id of 2 = 2
Id of 3 = 9
Id of 4 = 9
Id of 5 = 9
Id of 6 = 9
Id of 7 = 9
Id of 8 = 9
Id of 9 = 9