Disjoint Set

Disjoint Set에 대해 알아보려고 한다. 보다 자세한 부분은 아래 페이지를 확인하면 된다.

(https://www.geeksforgeeks.org/union-find/)

Disjoint Set 자료 구조의 정의를 먼저 살펴보면 여러 개의 분리된 하위 집합(Subset)으로 분할된 여러 집합을 기록하는 자료 구조이다.

일반적으로 Disjoint Set을 Union-Find로 불리기도 하는데 이는 내부적으로 Union-Find 알고리즘이 사용되기 때문이다. 

잠시 해당 알고리즘을 살펴보면, (정의된 명명처럼 union 및 find 작업을 수행한다.)

1) Find : 어느 특정한 요소가 어느 하위 집합에 있는지 찾는 작업 (보통 두 요소가 같은 하위 집합에 있는지 찾을 때 사용된다.)

2) Union : 두 하위 집합을 하나로 묶는다.

다시 돌아와서 Union-Find 알고리즘은 undirected graph에서 순환이 있는지 없는지 검사하기 위해 사용된다. (물론 다른 방법으로 순환 검사를 할 수 있다.)

그렇다면 각각의 노드에서 Self-loops(자기 자신 순환)이 없다는 가정하에 Union-Find 알고리즘을 살펴보도록 하자.

위의 undirected graph를 살펴보면, 각 edge에서 하위 집합을 만들 수 있다. (하나의 edge에 연결된 양쪽의 vertex를 사용하여)

이를 위해 Parent[] 배열을 만들고 하나씩 채워나가면,

0   1   2
-1 -1  -1 

먼저 Parent의 초기값은 -1로, 각 Vertex에 대해 할당하면 위의 값과 같다. (위는 Vertex 번호, 아래는 각 Vertex에 대한 Parent 값)

만들어진 초기 시점은 서로 다른 하위 집합에 속해 있다. 그렇다면 edge를 하나씩 찾아서 연결해보면,

0   1   2    <----- 1 is made parent of 0 (1 is now representative of subset {0, 1})
1  -1  -1

Edge 0-1 즉, Vertex 0과 1이 속해있는 하위 집합을 찾아보자. 맨 위에서도 확인 할 수 있듯이, Vertex 0과 1은 서로 다른 하위 집합에 포함되어 있다.

따라서 서로 union 할 수 있는데 어느쪽이 Parent가 되도 상관은 없다.

0   1   2    <----- 2 is made parent of 1 (2 is now representative of subset {0, 1, 2})
1   2  -1

다음으로 Edge 1-2 즉, Vertex 1과 2가 속해있는 하위 집합을 찾아보자.

여기까지 찾아봤을 경우에 하위 집합은 {0, 1, 2}가 된다. 그리고 Edge 2-0을 찾으면 모든 Vertex가 순환되는 것을 알 수 있다.

지금까지 한 것을 코드로 살펴보면 아래와 같다.

# Python Program for union-find algorithm to detect cycle in a undirected graph  # we have one egde for any two vertex i.e 1-2 is either 1-2 or 2-1 but not both from collections import defaultdict # This class represents a undirected graph using adjacency list representation class Graph: def __init__(self, vertices): self.V = vertices # No. of vertices self.graph = defaultdict(list) # default dictionary to store graph # function to add an edge to graph def addEdge(self, u, v): self.graph[u].append(v) # A utility function to find the subset of an element i def find_parent(self, parent, i): if parent[i] == -1: return i if parent[i] != -1: return self.find_parent(parent, parent[i]) # A utility function to do union of two subsets def union(self, parent, x, y): x_set = self.find_parent(parent, x) y_set = self.find_parent(parent, y) parent[x_set] = y_set # The main function to check whether a given graph # contains cycle or not def isCyclic(self): # Allocate memory for creating V subsets and # Initialize all subsets as single element sets parent = [-1] * (self.V) # Iterate through all edges of graph, find subset of both # vertices of every edge, if both subsets are same, then # there is cycle in graph. for i in self.graph: for j in self.graph[i]: x = self.find_parent(parent, i) y = self.find_parent(parent, j) if x == y: return True self.union(parent, x, y)

Union-Find 알고리즘을 바탕으로한 그래프 순환 검증하는 부분은 생각보다 간단하다. 위에서도 언급했듯이 각 Vertex의 Parent 배열을 만들어 해당 Vertex의 최상위 Parent를 찾고 다른 Vertex의 최상위 Parent와 비교하는 것이 전부이다. 더군다나 Union 또한 x, y일 경우 x의 부모 Vertex를 y로 놓는 것이다.

하지만 코드가 보기 쉬운 것처럼 union이나 find 작업은 O(n)의 시간(Worst Case)이 걸릴 수 있다. 좀더 개선된 알고리즘은 O(Logn)으로 Union by Rank 또는 Height를 사용하는 것으로 이후 포스팅에서 알아보도록 하겠다.