이후 정렬된 간선들을 하나씩 선택하여 사이클이 형성되는지 확인하고, 사이클이 형성되지 않는다면 $A$에 포함시킨다.
3번의 수행을 $|A| = N - 1$이 될 때 까지 수행한다.($N$은 정점의 개수)
이때 사이클이 형성되는지를 어떻게 알 수 있는지를 아직 확인하지 않았다. 이번 글에서는 사이클을 어떻게 판별할 수 있는지에 대해 알아볼 것이다.
접근
다음과 같은 상황을 가정해보자
간선들의 오름차순 정보와 $A$를 무시하고 그래프만 놓고 보았을 때. 다음과 같이 생각할 수 있다.
각 정점을 하나의 집합(Set)으로 생각하고, 간선이 이어진 상태를 두 집합이 합쳐졌다(Union)라고 할 수 있다.
그렇다면 $A$는 이러한 집합들을 모은 하나의 집합이다. 즉, 집합을 원소로 가지는 집합이다.
그렇다면, 위의 그래프에서 집합들은 아래와 같이 나타날 수 있을 것이다.
$\{1, 2\}, \{3, 9, 6, 7, 8\}, \{4\}, \{5\}$
이때, 이 집합들을 하나의 Tree로 표현할 수 있다. 단 루트가 누가 되던지는 상관없으며, 자식은 부모를 가리키는 상향식 트리어야 한다.
이러한 집합을 disjoint set(서로소 집합)이라고 부른다.
이때 어떤 간선을 선택하여 그 간선에 속한 두 노드가 동일한 집합이라면, 사이클이 형성된다.
왜냐하면, 동일한 집합이라는 말은 이미 어떤 방식이든, 두 정점이 연결되어 있다는 것을 의미한다. 이때, 동일한 집합의 두 정점을 잇는 간선을 다시 선택한다면, 두 정점을 연결하는 경로가 2개가 된다는 것을 의미한다.
이는 곧, 사이클이 형성된다고 할 수 있다.
Union-Find(or Disjoint Set)
서로소 집합(disjoint set) 또는 유니온 파인드 자료구조는 위에서 요구하는 "어떤 두 원소가 동일 집합에 존재하는가"라는 문제를 해결할 수 있는 자료구조이다.
또한 어떤 원소를 다른 집합에 포함시키는 연산(Union)도 지원한다.
이러한 자료구조를 표현하는 방법은 꽤 간단한데. 바로 배열을 이용하는 것이다. 위의 그래프에서 각 집합들을 트리로 표현하면 아래와 같이 나타낼 수 있다.
각각의 집합을 트리로 표현하려면 복잡할 것 같지만 어차피 우리는 이 집합 트리에서 부모가 누구인가만 알 수 있으면 상관없다. 따라서 정점만큼의 배열을 선언하여, 그 배열의 각 인덱스를 정점으로 할 때, $p[i]$의 값을 그 정점의 부모값을 저장하도록 하면 된다.
위의 트리들을 배열로 표현한다면 아래와 같을 것이다.
이제 parent 배열을 완성했으니 유니온 파인드 자료구조의 기본적인 연산을 알아보자
FindSet
FindSet 연산은 유니온 파인드 자료구조에서 find를 담당한다. 입력으로 받은 정점이 속한 트리의 루트가 누구인지를 찾고, 루트를 반환한다.
매우 심플하게 구현할 수 있는데 아래와 같이 구현할 수 있다.
find(v){
if(v == p[v]){
return v
}
return find(v);
}
해당 연산의 시간복잡도는 $O(h)$로 이때 $h$는 트리의 높이이다.
최악의 경우에서 트리가 편향된 경우, 연결 리스트와 같이 각 원소들을 쭉 따라가야 하므로 $O(n)$이 걸린다.
Union
Union 연산은 유니온 파인드에서 union을 담당하며 한 트리의 루트를 다른 트리의 루트의 자식 노드로 만드는 연산이다.
조금 복잡하게 들릴 수 있는데 간단하게 설명하자면 두 집합을 합하는 연산이다.
이 그래프에서 만약 간선 $E(2, 3)$을 선택했다고 생각한다면 집합 $\{1, 2\}$ 와 $\{3, 9, 6, 7, 8\}$은 하나의 집합으로 합할 수 있다.
이를 그림으로 표현하면 아래와 같게 될 것이다.
그림만 보면 복잡해 보인다. 하지만 매우 간단하게 구현할 수 있는데. 루트 노드를 자식 노드로 이동하는 것이기 때문에 둘 중 하나의 루트 노드의 값을 다른 하나의 루트 노드 값으로 변경시키면 끝난다.
구현은 아래와 같이 할 수 있다.
union(u, v){
x = find(u);
y = find(v);
p[x] = y;
}
Union의 시간복잡도는 find의 연산에 따라 좌우된다. 만약 find를 통해 루트 노드를 찾은 이후에는 값의 갱신만 하면 되므로 $O(1)$이다. 하지만 이 루트를 찾는 find()연산이 최악의 경우에 $O(h)$가 되기 때문에 결론적으로 $O(h)$가 되며 편향된 트리 상에서 $O(N)$이 될 수 있다.
Kruskal 알고리즘의 러프한 구현
이제 어떻게 사이클이 이루어지는가에 대한 감지 방식도 살펴보았으니 Kruskal 알고리즘을 의사 코드적으로 만들어 볼 수 있다.
Kruskal의 알고리즘은 아래와 같다.
Kruskal(G, w):
A = {}
for v in V:
makeDisjointSet(v)
sort edges of E into nondecreasing order by weight w
for each edge E(u, v) in E:
if find(u) != find(v):
A = A union {E(u, v)}
union(u, v)
return A
아직 의사코드이지만 지금까지 MST를 구하는 정형화된 알고리즘과, Kruskal 알고리즘의 이론적 접근을 이해했다면 왜 이렇게 구현해햐 하는지에 대해 이해할 수 있을 것이다.
해당 알고리즘의 시간복잡도는 다음과 같이 계산할 수 있다.
모든 간선에 대하여 하나씩 살펴보는 경우는 일반적으로 정점의 수 - 1 개의 간선을 살펴보면 끝날 수 있으나 최악의 경우에는 모든 간선을 살펴보는 상황이 일어날 수 있다.
또한 이러한 루프마다. 즉, 간선을 하나 선택할 때 마다, 간선에 연결된 두 정점에 대해 find 연산을 통해 동일한 집합에 속해있는지를 확인해야 하고, 속해있지 않다면 union을 통해 연결시키면서 MST의 부분집합 $A$에 합쳐야 한다.
$|E| = M$이라고 생각하고, 일반적인 Union-Find자료구조의 시간 복잡도가 $O(h) \backsimeq O(N)$ 이기 때문에 Kruskal 알고리즘의 전체적인 시간복잡도는 러프하게 $O(MN)$으로 생각할 수 있다.즉 다항 시간 복잡도를 가진다.
Kruskal 알고리즘의 최적화
위의 시간복잡도는 Union-Find 자료구조를 매우 나이브하게 구현하였을 때 걸릴 수 있는 시간 복잡도이다. 약간의 최적화를 통하여 시간복잡도를 줄일 수 있다.
Weighted Union
해당 방식을 적용한 Union 연산은 다음과 같다.
한 트리의 루트를 다른 트리의 루트의 자식으로 만든다. 이때 작은 트리의 루트를 큰 트리의 루트의 자식으로 만들어야 한다.
즉 노드가 더 많은 트리의 자식으로 노드가 더 적은 트리의 루트가 들어가야 한다는 것이다. 이것은 꽤 간단하게 그 이유를 도출할 수 있다.
Union뿐만 아니라 Find의 경우에도, 루트를 찾기 위해서는 $O(h)$로 트리의 높이에 따라 성능의 차이가 심해질 수 있다. 즉, 트리의 높이를 가능한 낮게 유지할 수록 이 연산들의 시간 복잡도가 줄어든다.
사이즈가 큰 트리는 일반적으로, 사이즈가 작은 트리보다 높이가 크다고 생각할 수 있다. 이때, 작은 트리의 자식으로 큰 트리가 들어갈 경우 전체적인 높이가 오히려 늘어날 수 있을 것이다.
반대로, 큰 트리에 작은 트리가 자식으로 들어갈 경우, 트리의 높이가 더 높아지는 일은 없다. 따라서 높이를 최소화시켜야 한다 라는 조건에서는 큰 트리에 작은 트리가 자식으로 들어가야 한다는 것이 타당하게 된다.
대신 Weighted Union 방식을 적용하기 위해서는 사전에 각 트리의 노드의 개수들을 알고 있어야 하기 때문에, 트리의 사이즈를 저장하는 추가적인 배열이 필요하게 된다.
WeightedUnion(u, v):
x = find(u)
y = find(v)
if size[x] < size[y]:
p[x] = y
size[x] += size[y]
else:
p[y] = x
size[y] += size[x]
Path Compression
Path Compression 즉 경로 압축은 find 연산을 수행할 때 마다, 방문한 각 노드들이 직접 루트 노드를 가리키도록 하여평평한 트리 즉, 높이를 최소화하는 트리를 만들도록 할 수 있다.
한번 Path Compression을 수행한 노드들은 다이렉트로 루트 노드를 가리키고 있게 되므로 $O(1)$에 find를 수행할 수 있다.
구현도 기존의 find와 크게 차이나지 않는데, 탐색중인 노드의 배열 인덱스에 직접 루트를 찾아 갱신하도록 하는 1줄의 코드만 넣으면 된다.
find(x):
if x == p[x]:
return x
return p[x] = find(x)
Weighted Union과 Path Compression을 모두 적용한 Union-Find 자료구조를 이용하여 Kruskal 알고리즘을 구현할 경우 기존의 $O(MN)$에서 $O(M \log M)$까지 개선시킬 수 있다. ($M = |E|$)
정리
지금까지 사이클의 판정을 위한 자료구조인 Union-Find의 개념과 구현, 그리고 최적화까지 알아보았다. 다음글에서는 의사 코드로 구현된 Kruskal 알고리즘의 직접 구현을 수행해볼 것이다.
