정의

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);
        }
    }
}