CSC212 Union Find in Java
--D. Thiebaut (talk) 10:58, 25 November 2014 (EST)
Contents
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
Version 2: Fast
source
public class UnionFindFast {
static int[] id = null;
static int[] size = null;
static int noVertices = 0;
public static void initQuickFind( int n ) {
noVertices = n;
id = new int[noVertices];
size = new int[noVertices];
for ( int i=0; i<noVertices; i++ ) {
id[i] = i;
size[i] = 1;
}
}
/**
* 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;
if ( size[ id_p ] < size[ id_q ] ) {
id[id_p] = id_q;
size[id_p] += size[id_q];
}
else {
id[id_q] = id_p;
size[id_q] += size[id_p];
}
}
public static void displayQF( String caption ) {
System.out.println( caption );
System.out.print( "index : " );
for ( int i=0; i<noVertices; i++ )
System.out.print( String.format( "%3d ", i ) );
System.out.println();
System.out.print( "Id : " );
for ( int i=0; i<noVertices; i++ )
System.out.print( String.format( "%3d ", id[i] ) );
System.out.println();
System.out.print( "Size : " );
for ( int i=0; i<noVertices; i++ )
System.out.print( String.format( "%3d ", size[i] ) );
System.out.println( "\n" );
}
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
Version 3: Faster
source
public class UnionFindFaster {
static int[] id = null;
static int[] size = null;
static int noVertices = 0;
public static void initQuickFind(int n) {
noVertices = n;
id = new int[noVertices];
size = new int[noVertices];
for (int i = 0; i < noVertices; i++) {
id[i] = i;
size[i] = 1;
}
}
/**
* 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) {
if (id[p] == p)
return p;
int root = idOf(id[p]);
id[p] = root;
return root;
}
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;
if (size[id_p] < size[id_q]) {
id[id_p] = id_q;
size[id_p] += size[id_q];
} else {
id[id_q] = id_p;
size[id_q] += size[id_p];
}
}
public static void displayQF(String caption) {
System.out.println(caption);
System.out.print("index : ");
for (int i = 0; i < noVertices; i++)
System.out.print(String.format("%3d ", i));
System.out.println();
System.out.print("Id : ");
for (int i = 0; i < noVertices; i++)
System.out.print(String.format("%3d ", id[i]));
System.out.println();
System.out.print("Size : ");
for (int i = 0; i < noVertices; i++)
System.out.print(String.format("%3d ", size[i]));
System.out.println("\n");
}
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");
idOf( 5 );
displayQF("after id(5)");
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
after id(5)
index : 0 1 2 3 4 5 6 7 8 9
Id : 0 1 2 9 9 9 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
