[알고리즘][Graph] Disjoint Set #2 Union By Rank와 Path Compression

학습목표
1. 기존 Union-Find 알고리즘의 문제점을 파악
2. Union-Find의 O(h)을 O(log n)으로 변경하는 union by rank와 path compression에
대해서 학습

 

이전글

https://yonghwankim-dev.tistory.com/235

[알고리즘][Graph] Disjoint Set #1 무방향 그래프에서 싸이클 탐색

 

1. 기존 Union-Find 알고리즘의 문제점

이전글에서 Union-Find 알고리즘을 통하여 무방향 그래프에서 싸이클이 존재하는지 탐색하는 알고리즘을 구현하였습니다. Union-Find 알고리즘의 내용은 아래와 같았습니다.

	@Override
	public int find(int[] parent, int i) {
		if(parent[i]==-1)
		{
			return i;
		}
		return find(parent, parent[i]);
	}

	@Override
	public void union(int[] parent, int u, int v) {
		parent[u] = v;
	}

	@Override
	public boolean isCycle() {
		int[] parent = new int[V];
		
		for(int i=0;i<V;i++)
		{
			parent[i] = -1;
		}
		
		for(int i=0;i<edges.size();i++)
		{
			Edge edge = edges.get(i);
			
			int u = find(parent, edge.src);
			int v = find(parent, edge.dest);
			
			if(u==v)
			{
				return true;
			}
			union(parent, u, v);
		}
		return false;
	}

위와 같이 모든 에지들을 순회하면서 에지간의 노드들의 속해있는 부분집합을 탐색(find)하고 서로 소속이 다르다면 합집합하는 방식이었습니다.

 

위 연산중 find 연산이 문제점이 존재합니다. 현재 find 연산의 방식은 재귀적인 호출로 부모를 타고 올라가는 방식이기 때문입니다. 최악의 경우 트리의 높이만큼의 시간(선형적)이 소요될 수 있습니다. 아래의 예제는 4개의 요소 0,1,2,3이 합집합하는 과정입니다.

위의 합집합 결과에서 노드 1과 다른 노드 N이 find 연산을 수행한다면 노드 1같은 경우 자기가 속한 루트(3)를 찾기 위해서 계속해서 부모를 타고 올라가야 할 것이다. 즉, 트리의 높이가 h라면 최악의 경우 O(h)가 걸릴 것입니다.

 

위와 같은 문제점을 해결하기 위해서는 union by rank와 path compression 기술을 사용하여 해결할 수 있습니다. 2가지 기술을 사용하면 시간복잡도를 O(log n)으로 줄일 수 있습니다.

 

2. union by rank

union by rank의 핵심은 2개의 부분집합이 서로 병합할때 더작은 트리가 더 큰 트리 자식으로 병합되는 것입니다. 트리를 병합하기 전 두 트리의 크기를 비교하기 위해서 rank라는 수를 사용합니다. 두 트리의 루트 노드의 rank를 비교하여 rank가 더 작은 트리가 rank가 더 큰 트리의 자식으로 병합되는 것입니다. 주의할 점은 이 rank는 height과는 다르다는 점입니다.

 

만약 path compression(아래에서 소개할)이 사용되는 경우 rank가 항상 트리의 높이(height)과 동일하지는 않기 때문에 높이 대신 rank라는 용어가 선호됩니다. 또한 rank(높이 대신에)는 트리의 크기(size)로써 사용이 가능합니다.

 

아래의 예제는 union by rank 기술을 사용하여 위 예제와 동일하게 합집합하는 예제입니다.

• union을 호출하기 전에 각각의 노드가 속하는 부분집합의 루트를 탐색(find)하고 rank를 비교함
• 두 트리의 rank가 동일하면 왼쪽이 오른쪽의 자식이 되고 rank를 1 증가시킴
• 그 외의 경우엔 rank가 낮은 쪽의 트리가 더 큰 쪽의 트리의 자식이 됨

 

3. 경로 압축(Path Compression)

Path Compression 기술은 find 연산을 호출할때 트리의 높이를 평평하게 만드는 기술입니다. 어떤 요소 x에 대해서 find 연산을 호출하면 트리의 루트를 반환되게 합니다. find 연산을 호출하면 어떤 요소 x에서 x가 속한 트리의 루트까지 이동합니다. Path Compression의 핵심은 탐색된 루트 노드를 x의 부모로 만들어 모든 중간 노드를 다시 이동할 필요가 없도록 하는 것입니다. 만약 x가 서브트리의 루트라면 x 아래의 자식 노드에서 루트까지의 경로도 압축되는 것입니다.

 

아래의 예제는 부분집합 {0, 1, ... , 9}인 상태에서 노드 3을 대상으로 find 연산을 호출한 예제입니다.

find(3) 호출을 통하여 노드 3이 속하는 부분집합의 루트인 9를 탐색하기 위하여 부모 노드를 타고 올라갈 것입니다. find 연산을 재귀적으로 호출하여 타고 올라가는 과정에서 노드 3과 노드 0은 노드 4의 자식이 되었다가 최종적으로는 트리의 루트인 노드 9의 자식이 됩니다. 노드1과 노드2를 대상으로 find 연산을 호출하면 트리의 높이만큼 시간을 소요하지 않고 더 빠르게 루트를 찾을 수 있을 것입니다.

 

정리하면 union by rank와 path compression을 사용하면 기존 union-find 알고리즘의 시간복잡도인 O(h)를 O(log n)만큼 줄일 수 있습니다.

 

4. Java언어 기반 union-find 알고리즘에 union by rank와 path compression 기술 적용

아래의 예제는 이전글의 union-find 알고리즘에 union by rank와 path compression 기술을 적용하여 무방향 그래프에서 싸이클이 존재하는 체크하는 예제입니다.

public class UnDirectedGraph<E> implements Graph<E>{
	private int V; // 노드 개수
	private ArrayList<ArrayList<Node<E>>> adj;	// 인접리스트
	private Map<Integer,E> map;
	private ArrayList<Edge> edges;
	
	public UnDirectedGraph(int v) {
		V = v;
		adj = new ArrayList<ArrayList<Node<E>>>(v);
		for(int i=0;i<v;i++)
		{
			adj.add(new ArrayList<Node<E>>());
		}
		map = new HashMap<Integer, E>();
		edges = new ArrayList<Edge>();	
	}
	
	@Override
	public void addEdge(Node u, Node v) {
		if(!map.containsKey(u.num))
		{
			map.put(u.num, (E) u.value);
		}
		if(!map.containsKey(v.num))
		{
			map.put(v.num, (E) v.value);
		}
		
		adj.get(u.num).add(v);
		adj.get(v.num).add(u);

		edges.add(new Edge(u.num,v.num));
	}

	@Override
	public int find(Subset[] subsets, int i)
	{
		if(subsets[i].parent!=i)
		{
			subsets[i].parent = find(subsets, subsets[i].parent);
		}
		return subsets[i].parent;
	}
	
	@Override
	public void union(Subset[] subsets, int x, int y)
	{
		int xroot = find(subsets, x);
		int yroot = find(subsets, y);
		
		if(subsets[xroot].rank < subsets[yroot].rank)
		{
			subsets[xroot].parent = yroot;
		}
		else if(subsets[xroot].rank > subsets[yroot].rank)
		{
			subsets[yroot].parent = xroot;
		}
		else
		{
			subsets[xroot].parent = yroot;
			subsets[yroot].rank++;
		}	
	}
	
	@Override
	public boolean isCycle()
	{
		Subset[] subsets = new Subset[V];
		for(int v=0;v<V;v++)
		{
			subsets[v] = new Subset();
			subsets[v].parent = v;
			subsets[v].rank = 0;
		}
		
		for (int e = 0; e < edges.size(); e++) {
            int x = find(subsets, edges.get(e).src);
            int y = find(subsets, edges.get(e).dest);
            if (x == y)
            {
            	return true;
            }
            union(subsets, x, y);
        }
		return false;
	}
}

public class Driver {

	public static void main(String[] args) {
		int V = 3;
		UnDirectedGraph<Integer> unDirectedGraph = new UnDirectedGraph<Integer>(V);
		
		Node<Integer> node0 = new Node<Integer>(0, 0);
		Node<Integer> node1 = new Node<Integer>(1, 1);
		Node<Integer> node2 = new Node<Integer>(2, 2);
		
		
		unDirectedGraph.addEdge(node0, node1);
		unDirectedGraph.addEdge(node0, node2);
		unDirectedGraph.addEdge(node1, node2);
		
		if(unDirectedGraph.isCycle())
		{
			System.out.println("이 그래프는 싸이클이 존재합니다.");
		}
		else
		{
			System.out.println("이 그래프는 싸이클이 존재하지 않습니다.");
		}
	}

}

이 그래프는 싸이클이 존재합니다.

 

5. union by rank와 path compression 기술을 적용한 union-find 알고리즘 시간복잡도

두 기술을 적용한 find 연산의 시간복잡도는 O(log₂*N)입니다. log₂N는 N<=1이 될때까지 log₂를 취한 횟수입니다.

N	log₂N
1	0
2	1
4	2
16	3
65536	4
2^65536	5

union-find 연산의 시간복잡도는 O(N+Mlog₂*N)입니다. 여기서 N은 노드의 개수이고, M은 에지의 개수입니다. 하지만 상수는 제거되므로 O(log₂*N)이게 되고 O(log₂*N)은 상수 시간을 가지게 되어 결과적으로 O(1)을 가지게 됩니다.

 

union-find 알고리즘 시간복잡도 : O(1)

 

 

References

Source Code : https://github.com/yonghwankim-dev/inflearn_algorithm/tree/master/graph/graph07_disjointset_pathcompression
Geeks For Geeks : https://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/