최소 신장 트리 문제란?
- 정의
"정점(vertex)의 집합 V와 가중치를 갖는 에지(edge)의 집합 E로 구성된 그래프 G = (V, E)가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리 T를 구하시오"
- 신장 트리 : 주어진 연결 그래프에서 사이클을 형성하는 간선을 제거하여 만든 트리
- 정점의 수가 n 개이면 신장 트리의 간선 수는 n-1 개
- 최소 신장 트리(MST): 주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분(간선)들의 가중치 합이 최소인 트리
- ex) 상수도관 네트워크, 도로 네트워크 설계
Example)
지도상에 여덟 개의 마을이 있고, 모든 마을이 서로 연결될 수 있도록 도로를 설계한다고 해보자.
- 연결된 도로는 사이클을 구성하면 안 된다.
- 연결된 도로의 전체 길이는 최소가 되어야 한다.
- 모든 도로는 양방향으로 상호 이동할 수 있다고 가정한다
이 문제를 표현하기 위해서는 그래프 자료구조를 사용하는 것이 좋다.
최소 신장 트리 T를 구하는 알고리즘(크루스칼 최소 신장 트리 알고리즘)
- 그래프 G의 모든 에지를 최소 힙 H에 추가한다.
- H로부터 에지 e를 하나 꺼낸다. 당연히 e는 모든 에지중에서 가장 가중치가 작은 에지이다.
- e의 양 끝 정점이 이미 T에 있는 경우, e로 인해 T에서 사이클이 발생할 수 있으므로 이런 경우에는 e를 버리고 2단계로 이동한다.
- 최소 신장 트리 T에 e를 추가하고 2단계로 이동한다.
- 2단계부터 4단계까지를 반복하면서 가장 작은 가중치의 에지를 찾고, 이 에지에 의해 사이클이 발생하지 않으면 해당 에지와 양 끝 정점을 최종 솔루션에 추가한다.
- 이렇게 선택된 에지와 정점은 최소 신장 트리를 구성한다.
- 매 반복 마다 최소 에지 가중치를 선택하기 때문에 그리디 방식이라고 한다.
- 이 알고리즘을 크루스칼 최소 신장 트리 알고리즘이라고 부른다.
슈도 코드
KruskalMST(G)
입력: 가중치 그래프 G=(V,E), |V|=n , |E|=m
출력: 최소 신장 트리 T
1. 가중치의 오름차순으로 선분들을 정렬한다. 정렬된 선분 리스트를 L이라고 하자.
2. 𝑇 = ∅ // 트리 T를 초기화시킨다.
3. while ( T의 선분 수 < n-1 ) {
4. L에서 가장 작은 가중치를 가진 선분 e를 가져오고, e를 L에서 제거한다.
5. if (선분 e가 T에 추가되어 사이클을 만들지 않으면) // feasibility check
6. e를 T에 추가시킨다.
7. else // e가 T에 추가되어 사이클이 만들어지는 경우
8. e를 버린다.
}
9. return 트리 T // T는 최소 신장 트리이다.
최소 신장 트리 알고리즘은 그리디 알고리즘 요건을 만족할까?
- 최적 부분 구조
- 증명하기 위해 귀류법을 사용해보자.
- MST 문제가 최적 부분 구조 속성을 가지지 않는다고 가정해보자.
- 즉, MST가 더 작은 MST 신장 트리의 집합으로 구성되지 않는다고 가정하는 것이다.
- 그래프 G의 정점으로 구성된 최소 신장트리 T가 있다고 가정한다. T에서 에지 e를 하나 선택하여 제거한다. e를 제거하면 T가 더 작은 트리인 T1과 T2로 나눠진다
- MST 문제가 최적 부분 구조 속성을 갖지 않는다고 가정했으므로 T1보다 더 작은 가중치를 갖는 신장트리 T1'이 존재해야 한다. 이 신장 트리 T1'과 T2를 에지 e로 연결한 새로운 신장 트리를 T'이라고 해보자
- T'의 전체 가중치가 T의 전체 가중치보다 작기 때문에 처음에 T가 최소 신장 트리라고 가정했던 가설이 틀리게 된다. 따라서 MST 문제는 최적 부분 구조 속성을 만족해야 한다
- 그리디 선택
- MST 문제가 그리디 선택 속성을 갖는다면 정점 v와 연결된 에지 중에서 최소 가중치 에지는 반드시 최소 신장 트리 T에 속해야 한다.
- 귀류법을 이용해보자
- 정점 v에 연결되어 있는 에지 중에서 최소 가중치를 갖는 에지를 (u, v)라고 가정한다
- (u, v)가 T에 속하지 않는다면 T는 v와 연결되어 있는 다른 에지를 포함해야 한다. 이 에지를 (x, v)라고 가정한다. (u, v)가 최소 가중치 에지이기 때문에, (x, v)의 가중치는 (u, v) 가중치보다 커야 한다
- T에서 (x, v)를 제거하고 (u, v)를 추가할 경우, 전체 가중치가 더 작은 트리를 얻을 수 있다. 이는 T가 최소 신장 트리라는 가정에 위배된다. 그러므로 MST 문제는 그리디 선택 속성을 만족해야 한다.
사이클을 판단하는 방법
그래프 에지 정보를 저장할 자료 구조가 필요하고, 새로운 에지를 추가할 때 사이클이 발생하는지를 판단하는 기능이 필요하다.
- 디스조인트-셋 자료구조(분리 집합)를 사용하면 해결할 수 있다.
분리 집합 자료구조에 대한 내용은 [자료구조]에 따로 정리해 두긴 했지만, 복습차원에서 다시 살펴보자
- 디스조인트-셋(분리 집합) 또는 유니온 파인드(Union-Find) 자료구조는 트리 형태의 원소로 구성된 포레스트이다.
- 각각의 원소는 숫자 ID에 표현되며, 랭크와 부모에 대한 포인터를 가진다.
- 디스조인트-셋 자료 구조가 초기화되면 랭크가 0인 N개의 독립적인 원소가 생성되며, 각 원소는 하나의 트리를 나타낸다
- 디스조인트-셋 연산
- make-set(x) : x를 ID로 갖는 원소를 디스조인트-셋 자료구조에 추가한다. 추가한 원소의 랭크는 0이고, 원소의 부모 포인터는 자기 자신을 가리키도록 설정한다
- find(x) : 원소 x에서 시작해서 부모 포인터를 따라 반복적으로 이동하여 트리의 루트를 반환한다. (루트의 부모는 루트 자신이다)
- union(x, y) : 두 개의 원소 x와 y에 대해 union() 연산을 수행하면 먼저 x와 y의 루트를 찾는다.
- 두 루트가 같다면 x와 y가 같은 트리에 속해 있음을 의미한다 --> 아무런 작업도 하지 않는다
- 두 개의 루트가 다르다면 높은 랭크 루트를 낮은 랭크 루트의 부모로 설정한다
이제, 디스조인트-셋 자료구조를 사용하여 크루스칼 MST를 구현하는 방법을 살펴보자
- 그래프의 정점 개수가 N이라면, 먼저 N개의 원소를 갖는 디스조인트-셋 자료 구조를 초기화한다.
- 크루스칼 알고리즘 2, 3단계에선 최소 힙을 이용하여 가장 가중치가 작은 에지를 선택하고, 사이클 발생 여부를 검사한다
- 이 때, 사이클 발생 여부를 검사하기 위해 디스조인트-셋의 union(x, y) 연산을 활용하자
- x, y의 부모가 같다면, 사이클을 형성할 수 있다. 따라서 union(x, y)에서 x, y의 루트가 같으면 아무 작업 없이 그대로 종료하고, MST에 추가하지 않는다
- union(x, y) 연산을 수행하여 실제로 두 트리가 병합하면 해당 에지를 MST에 추가한다
크루스칼 MST 알고리즘 구현(C++)
disjoint-set 클래스 정의
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
class SimpleDisjointSet
{
private:
struct Node
{
unsigned id;
unsigned rank;
unsigned parent;
Node(unsigned _id) : id(_id), rank(0), parent(_id) {}
bool operator!= (const Node& n) const
{
return this->id != n.id;
}
};
// 디스조인트-셋 포레스트
vector<Node> nodes;
public:
SimpleDisjointSet(unsigned N)
{
nodes.reserve(N);
}
void make_set(const unsigned& x)
{
nodes.emplace_back(x);
}
unsigned find(unsigned x)
{
auto node_it = find_if(nodes.begin(), nodes.end(),
[x](auto n) { return n.id == x; });
unsigned node_id = (*node_it).id;
while (node_id != nodes[node_id].parent)
{
node_id = nodes[node_id].parent;
}
return node_id;
}
void union_sets(unsigned x, unsigned y)
{
auto root_x = find(x);
auto root_y = find(y);
// 만약 X와 Y가 같은 트리에 있다면 그대로 종료
if (root_x == root_y)
return;
// 작은 랭크의 트리를 큰 랭크의 트리 쪽으로 병합
if (nodes[root_x].rank > nodes[root_y].rank)
swap(root_x, root_y);
nodes[root_x].parent = nodes[root_y].parent;
nodes[root_y].rank++;
}
};
그래프 자료 구조를 표현을 위해 에지 리스트 방식을 사용한다.
Edge 구조체
template <typename T>
struct Edge
{
unsigned src;
unsigned dst;
T weight;
// Edge 객체 비교는 가중치를 이용
inline bool operator< (const Edge<T>& e) const
{
return this->weight < e.weight;
}
inline bool operator> (const Edge<T>& e) const
{
return this->weight > e.weight;
}
};
Graph 클래스 정의
template <typename T>
class Graph
{
public:
// N개의 정점으로 구성된 그래프
Graph(unsigned N) : V(N) {}
// 그래프의 정점 개수 반환
auto vertices() const { return V; }
// 전체 에지 리스트 반환
auto& edges() const { return edge_list; }
// 정점 v에서 나가는 모든 에지를 반환
auto edges(unsigned v) const
{
vector<Edge<T>> edges_from_v;
for (auto& e : edge_list)
{
if (e.src == v)
edges_from_v.emplace_back(e);
}
return edges_from_v;
}
void add_edge(Edge<T>&& e)
{
// 에지 양 끝 정점 ID가 유효한지 검사
if (e.src >= 1 && e.src <= V && e.dst >= 1 && e.dst <= V)
edge_list.emplace_back(e);
else
cerr << "에러: 유효 범위를 벗어난 정점!" << endl;
}
// 표준 출력 스트림 지원
template <typename U>
friend ostream& operator<< (ostream& os, const Graph<U>& G);
private:
unsigned V; // 정점 개수
vector<Edge<T>> edge_list;
};
template <typename U>
ostream& operator<< (ostream& os, const Graph<U>& G)
{
for (unsigned i = 1; i < G.vertices(); i++)
{
os << i << ":\t";
auto edges = G.edges(i);
for (auto& e : edges)
os << "{" << e.dst << ": " << e.weight << "}, ";
os << endl;
}
return os;
}
크루스칼 최소 신장 트리 알고리즘 구현
// 트리도 그래프로 표현할 수 있으므로 최소 신장 트리도 Graph 객체로 반환합니다.
// 다만 여기에는 사이클이 있으면 안됩니다.
template <typename T>
Graph<T> minimum_spanning_tree(const Graph<T>& G)
{
// 에지 가중치를 이용한 최소 힙 구성
priority_queue<Edge<T>, vector<Edge<T>>, greater<Edge<T>>> edge_min_heap;
// 모든 에지를 최소 힙에 추가
for (auto& e : G.edges())
edge_min_heap.push(e);
// 정점 개수에 해당하는 크기의 디스조인트-셋 자료 구조 생성 및 초기화
auto N = G.vertices();
SimpleDisjointSet dset(N);
for (unsigned i = 0; i < N; i++)
dset.make_set(i);
// 디스조인트-셋 자료 구조를 이용하여 최소 신장 트리 구하기
Graph<T> MST(N);
while (!edge_min_heap.empty())
{
// 최소 힙에서 최소 가중치 에지를 추출
auto e = edge_min_heap.top();
edge_min_heap.pop();
// 선택한 에지가 사이클을 생성하지 않으면 해당 에지를 MST에 추가
if (dset.find(e.src) != dset.find(e.dst))
{
MST.add_edge(Edge <T>{e.src, e.dst, e.weight});
dset.union_sets(e.src, e.dst);
}
}
return MST;
}
테스트 코드
int main()
{
using T = unsigned;
// 그래프 객체 생성
Graph<T> G(9);
map<unsigned, vector<pair<unsigned, T>>> edge_map;
edge_map[1] = {{2, 2}, {5, 3}};
edge_map[2] = {{1, 2}, {5, 5}, {4, 1}};
edge_map[3] = {{4, 2}, {7, 3}};
edge_map[4] = {{2, 1}, {3, 2}, {5, 2}, {6, 4}, {8, 5}};
edge_map[5] = {{1, 3}, {2, 5}, {4, 2}, {8, 3}};
edge_map[6] = {{4, 4}, {7, 4}, {8, 1}};
edge_map[7] = {{3, 3}, {6, 4}};
edge_map[8] = {{4, 5}, {5, 3}, {6, 1}};
for (auto& i : edge_map)
for (auto& j : i.second)
G.add_edge(Edge<T>{ i.first, j.first, j.second });
cout << "[입력 그래프]" << endl;
cout << G << endl;
Graph<T> MST = minimum_spanning_tree(G);
cout << "[최소 신장 트리]" << endl;
cout << MST;
}
시간 복잡도
- Disjoint-Set을 사용하지 않는 크루스칼 알고리즘의 시간 복잡도는 O(E log E)이다.
- 그러나 디스조인트-셋 자료 구조를 사용하면 O(Ea(V))로 줄어들며, a(v)는 아커만 함수의 역함수이다.
- 아커한 함수의 역함수는 로그 함수보다 훨씬 느리게 증가한다.
- 정점이 많은 그래프에서 큰 성능 차이가 발생할 수 있다.
이 외에도 최소 신장 트리를 찾는 프림 알고리즘이 존재하는데, 그래프 파트에서 다룰 예정이다
Ref) 코딩 테스트를 위한 자료 구조와 알고리즘 with C++
'Algorithm > Greedy' 카테고리의 다른 글
| [Algorithm/Greedy] 웰시-포웰 알고리즘(Welsh-Powell algorithm) (0) | 2024.07.04 |
|---|---|
| [Algorithm/Greedy] 그래프 컬러링 (0) | 2024.07.04 |
| [Algorithm/Greedy] 작업 스케줄링 문제 (0) | 2024.07.03 |
| [Algorithm/Greedy] 배낭 문제(knapsack problem) (0) | 2024.07.03 |
| [Algorithm/Greedy] 최단 작업 우선 스케줄링(shortest-job-first scheduling) (0) | 2024.07.03 |