1. 개념
Spanning Tree(스패닝 트리) 란?
그래프의 정점 모두와 간선의 부분 집합으로 구성된 부분 그래프이다. 스패닝 트리에 포함된 간선들은 정점들을 트리형태로 모두 연결 해야하며, 트리의 특성 상 사이클이 발생 해서는 안된다.
Minimum Spanning Tree(MST, 최소 스패닝 트리)
가중치 그래프의 스패닝 트리 중 가중치의 합이 가장 작은 트리를 최소 스패닝 트리라고 한다. 모든 노드를 최소한의 비용으로 잇는 그래프라고 생각하면 된다.
2. 대표적인 알고리즘 2가지
유니온 파인드 구조를 사용하는 Kruskal 알고리즘과 Dijstra 알고리즘과 비슷한 Prim 알고리즘이 존재한다
3. Kruskal Algorithm(크루스칼 알고리즘)
3.1. 아이디어
그래프의 모든 간선을 오름차순 정렬한 뒤, 가중치가 작은 순으로 스패닝 트리에 하나씩 추가한다. 이때 사이클이 발생하지 않게 노드를 추가해줘야한다.
3.2. 코드
앞서 작성한 유니온 파인드 구조를 사용하여 구현하게 된다
const int MAX_V=10000;
vector<pair<int,int>> adj[MAX_V]; //그래프의 인접 노드와의 정보를 담고 있음
int main(void){
//{가중치,(u,v)} 형식으로 저장. 이후 가중치 순으로 정렬.
vector<pair<int,pair<int,int>>> edges;
for(int u=0;u<N;u++){
for(int j=0;j<adj[u].size();j++){
int v=adj[u][j].first;
int cost=adj[u][j].second;
edges.push_back({cost,{u,v}});
}
}
sort(edges.begin(),edges.end()); //가중치 순으로 오름차순 정렬
DisjointSet sets(N);
int answer=0;
for(int i=0;i<edges.size();i++){
int cost=edges[i].first;
int u=edges[i].second.first;
int v=edges[i].second.second;
if(sets.find(u)==sets.find(v))
continue;
sets.merge(u,v);
answer+=cost;
}
return answer;
}3.3. 정당성 증명
가중치가 가장 작은 간선을 추가해 나가면 어떻게 최소 스패닝 트리가 되는 건지 이를 증명해보자.
최소 스패닝 트리는 스패닝 트리에 간선을 추가할 때 뒤에 오는 간선들은 생각하지 않고 지금 고를 수 있는 제일 작은 간선을 고른다(사이클 발생 시키는 것은 제외). 이는 그리디 알고리즘으로 분류 되며 그리디 알고리즘을 증명하기 위해서는
- 탐욕적 선택 속성
- 최적 부분 조건
위 두 가지를 보여야한다. 계속해서 최소 가중치의 간선을 선택해야 하므로 최적 부분 조건은 성립함을 알 수 있고, 탐욕적 선택 속성은 귀류법으로 증명할 수 있다.
탐욕적 선택 속성 증명 by 귀류법
Kruskal 알고리즘이 선택하는 간선 중 그래프의 최소 스패닝 트리 T에 포함 되지 않은 간선이 있다고 가정하자. 이 중 첫 번째로 선택되는 간선을 (u,v)로 부르자(위 사진상에서 20 가중치에 해당하는 간선). (u,v)는 T상에서 다른 경로로 이어져 있다. 이 경로를 이루는 간선 중 하나는 반드시 (u,v)와 가중치가 크거나 같아야 한다.
만약 이 간선들이 아래와 같이 (u,v) 보다 작다면 Kruskal 알고리즘은 (u,v)를 선택하기 이전에 그 경로들을 선택했을 것이고 (u,v)는 선택될 수 없었을 것이다. 그러므로 모순이 발생한다.
T에서 u,v를 이루는 경로 중 하나는 반드시 (u,v) 보다 크거나 같으므로 해당 간선을 (u,v)로 바꾸어도 스패닝 트리이며 가중치 총합은 줄거나 같게 된다. T 가 이미 MST라고 가정했으므로, 이 변경을 거친 결과는 (u,v)를 포함하는 최소 스패닝 트리가 된다.
3.4. 시간 복잡도
참고 자료
알고리즘 문제해결 전략(종만북)
