정의
spanning tree : spen(덮다)라는 말 처럼, 모든 정점을 포함하는 트리를 말함.
그 중에 최소(V-1개 edge를 가짐)를 찾는 것.
같은 비용인 2개 이상의 MST를 가질 수 있음.
용어 정리
- 안전간선(safe edge) : 루트 불변성을 유지하면서 안전하게 부분 신장트리 A에 추가할 수 있는 간선.
- 절단 : 그래프에 대해 (S,V-S)로 정점집합을 분리된 것.
- 교차한다(cross) : 간선(u,v)에 대해 하나는 S에 있고, 다른 하나는 V-S에 있으면, (u,v)는 절단(S,V-S)을 교차한다고 함.
- 존중한다(respect) : 신장트리 A에 절단을 건너는 간선이 없다면, 절단이 간선의 집합 A를 존중한다고 함.
- 경량간선(light edge) : 절단을 교차하는 간선 중 가중치가 최소인 간선.
특징
1. 신장트리 A에 경량간선(u,v)을 추가하면 (u,v)는 A에 대해 안전하다. => 프림 알고리즘 기초
2. 서로 다른 신장트리 A,B 에 대해 A와 B를 잇는 (u,v)가 경량간선이면 안전하다. => 크루스칼 기초
증명

크루스칼 알고리즘
E개 간선을 가중치가 감소하지 않는 순서로 정렬.
각 간선을 Greedy하게 MST에 추가.
(사이클 검사는 유니온 파인트로 쉽게 가능)
전체 수행 시간 : O(정렬+각 간선 추가 시도*유니온파인드) -> O(ElgV)
소스 코드
sort(EdgeList.begin(), EdgeList.end()); // 간선의 가중치에 따라 정렬
int mst_cost = 0;
UnionFind UF(V); // 각 정점이 여러개 그룹
for(int i = 0; i < E; ++i){
pair<int, ii> front = EdgeList[i]; // 정렬된 edge를 하나 가져와서
if (!UF.isSameSet(u, v)){ // u, v 정점이 같은 그룹인지 검사
mst_cost += asd; // 서로 다른 그룹이면 둘사이 (u,v)간선의 가중치 더함
UF.unionSet(); // 추가된 간선을 연결하고 하나의 그룹으로 만듬
}
}
위 코드는 마지막 간선까지 검사하지만 보통 그 전에 끝낼 수 있다.
예를 들어 정점 모두 방문하면 끝난다던지…
프림 알고리즘
하나의 정점을 선택해서 선택하지 않은 정점으로 가면서 MST를 구한다
우선순위 큐에 가중치가 증가하는 순서로 정렬되고, 거기서 하나씩 꺼내서 연결
(정점이 선택되지 않은것 == 사이클이 아닐때).
전체 수행 시간 : O(각 간선을 한번씩 처리 * 우선순위 큐 삽입,삭제 비용) -> O(ElgV)
소스 코드
priority_queue q; // STL 기본은 최대 힙
void process(int vtx){
taken[vtx] = 1; // 정점 선택 표시
for(int j = 0; j < adj[vtx].size(); ++j){ // vtx와 연결된 정점
int v = adj[vtx][j];
if (!taken(v)) // 방문하지 않으면
q.push(v);
}
}
void main(){
process(0); // 시작정점 0을 선택하고 모든 간선 처리
mst_cost = 0;
while(!q.empty()){
(u,v,w) = q.top(); q.pop(); // u(시작정점), 추가할 정점 v, 가중치 w
if (!taken[v]){
mst_cost += w;
process(v);
}
}
}
Leave A Comment