[Java] Union Find

最近把Union Find重新看過一次，並實際把Quick Find和Quick Union和改進實作一次。

Create

選擇種類，且輸入大小

Count

輸出組的數目

Find

輸出元素的節點

Connected

判斷兩元素是否同節點

Show

輸出所有元素的節點

Union

連結兩個節點

Main

package unionfind;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		QuickFind QF = new QuickFind(0);
		QuickUnion QU = new QuickUnion(0); 
		WeightedQuickUnion WQU = new WeightedQuickUnion(0); 
		WeightedQuickUnionPathCompress WQUPC = new WeightedQuickUnionPathCompress(0);
		
		Scanner scanner = new Scanner(System.in);
		
		int kind = 0 ;
		
		while(true)
		{
			String input ;
			System.out.println("Input your operation : create , count , find , union , connected , show , end ");
			input = scanner.next();
			if ( input.equals("end") )
			{
				break ;
			}
			else if ( input.equals("show") )
			{
				if ( kind == 0 )
					System.out.println("None");
				else if ( kind == 1 )
				{
					for ( int i = 0 ; i < QF.Element.length ; i ++ )
					{
						System.out.print(QF.Element[i]+ " ");
					}
					System.out.println();
				}
				else if ( kind == 2 )
				{
					for ( int i = 0 ; i < QU.Element.length ; i ++ )
					{
						System.out.print(QU.Element[i]+ " ");
					}
					System.out.println();
				}
				else if ( kind == 3 )
				{
					for ( int i = 0 ; i < WQU.Element.length ; i ++ )
					{
						System.out.print(WQU.Element[i]+ " ");
					}
					System.out.println();
				}
				else if ( kind == 4 )
				{
					for ( int i = 0 ; i < WQUPC.Element.length ; i ++ )
					{
						System.out.print(WQUPC.Element[i]+ " ");
					}
					System.out.println();
				}
			}
			else if ( input.equals("create"))
			{
				System.out.println("Input which kind of UnionFind you want to create (number) : 1.QuickFind , 2.QuickUnion , 3.WeightedQuickUnion , 4.WeightedQuickUnionPathCompress ");
				int n = scanner.nextInt();
				System.out.println("Input the size.") ;
				int m = 0 ;
				while ( m == 0 )
				{
					m = scanner.nextInt();
					if ( m == 0 )
						System.out.println("The size can't be zero, so please input again.") ;
				}
				if ( n == 1 )
				{
					kind = 1 ;
					QF = new QuickFind(m);
				}
				else if ( n == 2 )
				{
					kind = 2 ;
					QU = new QuickUnion(m);
				}
				else if ( n == 3 )
				{
					kind = 3 ;
					WQU = new WeightedQuickUnion(m);
				}
				else if ( n == 4 )
				{
					kind = 4 ;
					WQUPC = new WeightedQuickUnionPathCompress(m);
				}
			}
			else if ( input.equals("count") )
			{
				if ( kind == 0 )
					System.out.println("None") ;
				else if ( kind == 1 )
					System.out.println(QF.count) ;
				else if ( kind == 2 )
					System.out.println(QU.count) ;
				else if ( kind == 3 )
					System.out.println(WQU.count) ;
				else if ( kind == 4 )
					System.out.println(WQUPC.count) ;
			}
			else if ( input.equals("union"))
			{
				if ( kind == 0 )
					System.out.println("None") ;
				else
				{
					System.out.println("Input the two elements which you want to union.") ;
					int n = scanner.nextInt();
					int m = scanner.nextInt();
					if ( kind == 1 )
					{
						QF.union(n, m);
					}
					else if ( kind == 2 )
					{
						QU.union(n, m);
					}
					else if ( kind == 3 )
					{
						WQU.union(n, m);
					}
					else if ( kind == 4 )
					{
						WQUPC.union(n, m);
					}
				}
			}
			else if ( input.equals("find"))
			{
				if ( kind == 0 )
					System.out.println("None") ;
				else
				{
					System.out.println("Input the number.") ;
					int n = scanner.nextInt();
					if ( kind == 1 )
					{
						System.out.println(QF.find(n));
					}
					else if ( kind == 2 )
					{
						System.out.println(QU.find(n));
					}
					else if ( kind == 3 )
					{
						System.out.println(WQU.find(n));
					}
					else if ( kind == 4 )
					{
						System.out.println(WQUPC.find(n));
					}
				}
			}
			else if ( input.equals("connected"))
			{
				if ( kind == 0 )
					System.out.println("None") ;
				else
				{
					System.out.println("Input the two numbers.") ;
					int n = scanner.nextInt();
					int m = scanner.nextInt();
					if ( kind == 1 )
					{
						System.out.println(QF.connected(n,m));
					}
					else if ( kind == 2 )
					{
						System.out.println(QU.connected(n,m));
					}
					else if ( kind == 3 )
					{
						System.out.println(WQU.connected(n,m));
					}
					else if ( kind == 4 )
					{
						System.out.println(WQUPC.connected(n,m));
					}
				}
			}
		}
	}
}

QuickFind

package unionfind;

public class QuickFind {
	
	int[] Element ;
	int count ;
	
	public int count()
	{
		return count ;
	}
	
	public int find(int x)
	{
		return Element[x] ; 
	}
	
	public boolean connected(int x , int y)
	{
		return find(x) == find(y) ;
	}
	
	
	public void union(int x , int y)
	{
		int p_x = find(x) ;
		int p_y = find(y) ;
		if ( p_x == p_y )
			return ;
		else
		{
			for ( int i = 0 ; i < Element.length ; i ++ )
			{
				if ( Element[i] == p_x )
					Element[i] = p_y ;
			}
			count -- ;
		}
	}
	
	
	QuickFind(int x){
		count = x ;
		Element = new int[x] ;
		for ( int i = 0 ; i < x ; i ++ )
			Element[i] = i ;
	}
}

QuickUnion

和QuickFind比起來只改了find和union

public int find(int x)
{
	while ( x != Element[x]) 
		x = Element[x];  
	return x ; 
}

public void union(int x , int y)
{
	int r_x = find(x);  
	int r_y = find(y);  
	if (r_x == r_y)   
		return ;  
	else
	{
		Element[r_x] = r_y;   
		count--; 
	}
}

WeightedQuickUnion

另外創立一組Size[]來記錄每組大小，確保合併的時候小的為子樹

WeightedQuickUnion(int x){
	count = x ;
	Element = new int[x] ;
	Size = new int[x] ;
	for ( int i = 0 ; i < x ; i ++ )
	{
		Element[i] = i ;
		Size[i] = i ;
	}
}

public void union(int x , int y)
{
	int r_x = find(x);  
	int r_y = find(y);  
	if (r_x == r_y)   
		return ;  
	else
	{
		if (Size[r_x] < Size[r_y]) 
		{ 
			Element[r_x] = r_y ; 
			Size[r_y] += Size[r_x] ; 
		}  
		else 
		{ 
			Element[r_y] = r_x ; 
			Size[r_x] += Size[r_y] ; 
		}  
		count -- ;  
	}
}

WeightedQuickUnionPathCompress

只需在find加上一行代碼即可

public int find(int x)
{
	while ( x != Element[x]) 
	{
		Element[x] = Element[Element[x]];
		x = Element[x];
	}
	return x ; 
}