2024-06-11-21. Kruskal Algorithm, Union Find (Disjoint Set)
Minimum Spanning Tree 문제
각 간선이 양수 가중치 값을 가지는 무방향 그래프에서, 다음 두 조건을 만족하는 간선들의 집합을 찾는 문제를 Minimum Spanning Tree (최소 신장 트리) 문제라고 한다.
- 간선들은 모든 노드를 연결해야 한다. 즉, 임의의 두 노드에 대해, 선택된 간선으로 구성된 경로가 존재해야 한다.
- 간선들의 가중치 합이 최소가 되도록 선택해야 한다.
그래프에서 s → v1→ v2→ ... → vk → s 처럼 중복된 간선을 지나지 않고 처음 노드로 돌아오는 경로를 사이클이라 한다.
사이클에서는 간선 하나를 제외해도 사이클의 노드들이 연결된 상태를 유지한다.
따라서 최소 신장 트리 문제에서 선택된 간선들은 사이클을 이루어서는 안 된다. 사이클에서 간선 하나를 제거해 가중치 합을 줄일 수 있기 때문이다.
사이클이 존재하지 않는 그래프를 트리라고 한다. 이것이 최소 신장 트리라는 이름의 이유이다.
간선 하나를 추가해 하나의 노드를 연결할 수 있으므로, n개의 노드가 있는 그래프에서는 n-1개의 간선이 선택된다.
Kruskal Algorithm
최소 신장 트리 문제를 푸는 알고리즘으로는 Kruskal Algorithm이 있다.
크루스칼 알고리즘은 다음과 같이 실행된다.
- 가장 가중치가 작은 간선부터 차례대로 선택한다.
- 단, 간선을 추가했을 때 사이클이 생긴다면, 그 간선은 선택하지 않는다.
- n-1개의 간선이 선택될 때까지 반복한다.
정확성 증명은 다음과 같다.
- 최소 신장 트리의 간선들의 집합을 A라고 하자.
- 크루스칼 알고리즘에서 k개의 간선을 선택했을 때, 선택한 간선들이 A의 부분집합이라고 가정하자.
- k+1번째 추가한 간선 e는 A에 포함되지 않는다고 하자.
- A U e 에는 사이클이 존재한다.
- 증명 : e가 노드 u, v를 연결한다고 하자. u, v사이에 A의 간선들로 구성된 경로가 존재한다. 여기서 e가 추가되면, u에서 원래 경로를 따라 v에 도달한 후, 다시 e를 따라 u로 돌아갈 수 있다.
- A U e의 사이클의 간선들 중에는 크루스칼 알고리즘에서 선택하지 않은 간선이 있다. 크루스칼 알고리즘은 사이클이 생기지 않도록 간선을 선택하기 때문이다.
- 사이클의 간선들 중 크루스칼에서 선택하지 않은 하나를 고르자. 이 간선을 g라 하자.
- 사이클에서 간선 하나를 제거해도 노드들이 연결된 상태가 유지되므로, A U e에서 g를 제거하면 신장 트리가 된다. 이 집합을 A’이라 하자.
- 그런데 크루스칼에서 g대신 e를 선택했으므로, e의 가중치가 g의 가중치 이하이다.
- 따라서 A’의 가중치 합은 A의 가중치 합 이하가 된다.
- e가 g의 가중치보다 작다면 A가 최소 신장 트리가 아니게 되어 모순이다. g와 e의 가중치가 같다면, A’은 또다른 최소 신장 트리가 된다.
- 따라서 A에 없는 간선 e가 추가되었다면, A가 아닌 또다른 최소 신장 트리에 포함된다는 뜻이므로, 알고리즘은 k+1번째에도 정확하게 동작한다.
크루스칼 알고리즘을 구현하려면, 가장 가중치가 작은 간선을 찾는 방법과 특정 간선을 추가했을 때 사이클이 생기는지를 판단하는 방법을 알아야 한다.
가장 가중치가 작은 간선은 간선들을 순서대로 정렬하면 알 수 있다.
특정 간선을 추가했을 때 사이클이 추가되는지는 어떻게 알 수 있을까?
u와 v를 잇는 간선을 추가하기 전에, u에서 DFS를 시작해 v까지 마킹되는지를 확인할 수도 있을 것이다. 그런데 DFS는 O(n)이 걸린다. 간선 m개, 노드 n개인 그래프라면, 최대 m번 DFS를 반복해야 하므로 총 O(mn) 시간이 걸린다. 더 빠른 방법을 알아보자.
Union Find (Disjoint Set)
크루스칼 알고리즘에서 사이클이 생기는지 여부를 판단하는 데 Union Find를 이용한다.
Union Find는 다음과 같이 집합을 다룬다.
- N개의 원소가 존재한다고 하자.
- 초기에는 N개의 집합이 각각 1개의 원소를 가진다.
- 두 가지 연산이 있다.
- Union(a, b) : 원소 a와 b가 속한 두 개의 집합을 합친다.
- Find(a) : a가 속한 집합의 id를 리턴한다.
- Find(a) 와 Find(b)를 비교하여 a와 b가 같은 집합에 있는지를 판별할 수 있다.
Union Find를 어떻게 구현할 수 있을까? 다음과 같은 트리를 통해 구현한다.
- 각각의 원소는 노드로 만들어진다.
- 초기에는 하나의 노드로 구성된 N개의 트리가 존재한다.
- Union 연산이 진행된 이후에는
- 하나의 집합이 하나의 트리로 표현된다.
- 트리의 루트 노드가 해당 집합의 id이다.
- 그 외의 제한 조건은 없다.
- 노드는 키값과 부모 노드로의 포인터만 가지면 된다.
- 부모 노드로의 포인터는 id를 알아내기 위해 필요하다.
- 자식 노드 포인터는 필요 없다.
구체적으로는 다음과 같이 구현된다.
- Find(a)
- a 의 부모 노드 포인터를 따라가, 루트 노드를 리턴한다.
- Union(a, b)
- a와 b에 대해 각각의 루트 노드를 찾는다. 하나의 루트 노드가 다른 루트 노드의 자식 노드가 되어, 두 트리를 합친다.
- 연산 시간을 줄이기 위해선, 두 루트 노드 중 어떤 것이 최종적인 루트 노드가 되어야 할까?
- 노드 개수가 많은 쪽을 루트 노드로 하면, Find() 수행 시간을 O(logN)으로 할 수 있다.
- 증명 :
- 위 규칙에 따라 Union한다고 할 때, 특정 노드의 깊이가 늘어났다는 것은, 노드 개수가 더 많은 집합으로 합쳐졌다는 것이다.
- 따라서, 노드 깊이가 늘어날 때마다 속한 집합의 노드 개수가 최소 2배가 된다.
- 깊이가 k라면 노드 개수는 최소 2k개가 된다.
- 가장 깊이가 깊은 노드의 깊이가 h라면, Find() 수행 시간은 O(h)이며, 노드 개수는 최소 2h이다.
- 노드 개수를 N이라 하면, 2h<=N, h <= logN
- Find 수행 시간이 O(logN)임이 증명되었다.
- Find에서 루트 노드를 찾아가는 과정에서, 해당 경로에 있는 노드들을 모두 루트 노드의 자식으로 옮길 수도 있다.
- 이러한 추가 연산을 하면 Union과 Find에 O(α(N)) 시간이 걸린다.
- α 는 log* 보다 느리게 증가하는 함수이다. log*는 로그를 반복적으로 적용하는 함수이다.
- 즉, 상수 시간과 비슷할 정도로 수행시간이 빠르다.
Union Find (Disjoint Set) 을 통한 사이클 판정
Kruskal Algorithm에서 Union Find를 통해 사이클을 판정하는 방법은 다음과 같다.
- 먼저 각 노드에 대해 Union Find 노드를 생성한다.
- Kruskal 알고리즘에서 노드 u, v를 연결하는 간선을 추가했다면, Union(u, v)를 실행한다.
- u, v를 연결하는 간선을 추가할 때 사이클이 생기는지 판단하려면, Find(u)==Find(v)를 수행한다.