최소신장트리 (Minimum Spanning Tree) - 프림 알고리즘

1. MST란

MST, 최소 신장 트리 (Minimum Spanning Tree)란?

MST란, 가중치가 있는 무방향성 그래프 (weighted undirected graph)가 주어졌을 때, 모든 vertex를 연결할 수 있도록 edge를 선택하는데 그 가중치의 합(비용)이 최소가 되도록 하는 edge set을 말한다.

MST 알고리즘을 통해 구한 edge들로만 그래프를 재구성하면, 임의의 vertex a와 b사이에는 항상 경로가 존재하며, 그래프에서는 cycle이 없다.

이를 구하기 위한 방법으로는 대표적으로 프림 알고리즘과 크루스칼 알고리즘이 있다.

프림 알고리즘은 우선순위 큐를 이용해서, 크루스칼은 union-find를 이용해서 해결한다.

MST 특성

MST는 다음과 같은 특성을 지닌다. [참고]

(1) Possible Multiplicity: 비용이 최소가 되는 MST를 구했더라도, 같은 비용을 갖는 다른 구성의 MST가 존재할 수 있다.

(2) Uniqueness: 만약 edge들이 다 다른 가중치를 갖는다면, 오로지 하나의 MST만 존재한다. 증명은 위키에

(3) Minimum-cost Subset: 만약 가중치들이 양수라면, MST는 모든 vertex들을 이어주는 최소 비용의 부분 그래프이다.

(4) Cycle Property: 그래프에서 cycle C에 존재하는 edge들 중에서 가중치가 가장 큰 edge는 MST에 포함될 수 없다. (가중치가 가장 큰 edge가 여러 개인 경우는 아님)

(5) Cut property: 그래프의 cut으로 구분된 두 부분 그래프 S와 V-S에서, 두 부분 그래프를 이어줄 수 있는 cut-set의 edge 중에서 가중치가 가장 작은 edge는 MST에 포함된다. (가중치가 가장 작은 edge가 여러개인 경우에는 아님)

(6) Minimum-cost edge: 만약 그래프 중에서 최소 가중치를 갖는 edge e가 딱 하나 있다면, 해당 그래프의 다양한 MST에 항상 존재한다.

 

2. 프림 알고리즘

프림 알고리즘은 하나의 노드에서 시작하여, 가중치가 가장 작은 edge를 합쳐 나가며 MST를 만두는 방법이다. 이 과정에서 가중치가 가장 작은 edge를 선택하기 위해 최소 priority queue (최소 heap)를 사용한다.

(1) 초기 환경이 다음과 같다고 하자.

프림 알고리즘에서 시작 vertex는 임의로 정해도 상관이 없다. 결국 모든 vertex를 포함시킬 것이니까. 그래서 A에서 시작한다고 하자.

(2) 노드 A 선택

노드 A에서는 "4의 비용으로 B"를, "5의 비용으로 D"를, "2의 비용으로 E"를 갈 수 있다. 노드 A에서 도달가능 한 vertex들을 우선순위 큐에 가중치를 기준으로 넣어주자!

그리고 우선순위 큐를 확인하면 vertex E가 2의 비용으로 가장 작은 것을 알 수 있다. 우선순위 큐에서 E를 pop해준다. 이 과정에서 비용 2의 edge AE는 선택된 것이고, MST에 포함된다.

(3) 노드 E 선택

이제 E에서 접근 가능한 vertex들을 추가한다. 3의 비용으로 B를, 8의 비용으로 D를, 7의 비용으로 F를, 11의 비용으로 C를 갈 수 있다. 무방향 그래프임을 고려하면, 노드 E에서 노드 A는 2의 비용으로 갈 수 있긴 하다. 하지만 노드 A의 색깔은 이미 파란색이고, 처리가 완료되었으므로 추가하지 않는다.

이제 우선순위 큐를 확인해서, 가장 작은 가중치 3을 갖는 vertex B를 선택한다.

(4) 노드 B선택

B에서는 노드 D를 1로 갈 수 있다. (3)에서와 마찬가지로 A, E는 이미 처리 완료했으므로, 해당 vertex로 갈 수 있는 edge는 우선순위 큐에 추가하지 않는다.

이제 D를 뽑자!

(5) 노드 D 선택

노드 D에서는 A (비용 5)와 B (비용 1), E (비용 8)가 이미 처리되었으므로 추가할 edge가 없다.

우선순위 큐에서 노드 B는 이미 처리되었다. Pop을 하고, 아무런 작업을 수행하지 않는다.

(6) 가중치 4, vertex B pop

우선순위 큐에서 4, B만 뽑았고 아무런 작업을 하지 않았으므로, 그림에서는 오른쪽 표만 바뀌었다. 마찬가지로 이번에 pop할 D도 처리된 노드이므로, pop만 하고 아무런 작업을 하지 않는다.

(7) 가중치 5, vertex D pop

우선순위 큐에서 이제 7의 비용으로 갈 수 있는 F를 뽑자.

(8) 노드 F 선택

F에서 갈 수 있는 가중치 12의 C와 가중치 4의 G를 우선순위 큐에 추가한다.

그러면 4의 비용으로 연결할 수 있는 G가 우선순위 큐에서 다음으로 뽑히게 된다.

(9) 노드 G 선택

똑같은 과정으로 G에서 갈 수 있는 가중치 5의 C를 추가한다. 그리고 해당 edge가 가장 작으므로 pop하여 처리한다.

(10) 노드 C 선택

우선순위 큐에 (8, D), (11, C), (12, C)가 남아있다. 하지만 vertex D와 vertex C는 모두 처리가 완료된 vertex이므로 전부 제거만 하고 아무런 작업을 하지 않는다.

(11) 완성

MST가 완성되었다! 비용은 22이다.

MST 특성 (1)에서 적힌 것처럼, 그래프의 구성에 따라 다양한 MST가 존재할 수 있다. 다만 이번 예제는 MST 특성 (2)에서 설명하는 것처럼, 모든 edge의 비용이 다 다르므로 유일하다.

다양한 MST가 존재하는 그래프

3. 시간복잡도

우리가 사용하는 우선순위 큐는 추가와 삭제에 $O(log N)$의 시간복잡도를 갖는다.

 

vertex를 하나 탐색할 때마다, 연결된 모든 edge를 우선순위 큐에 추가한다. 검색할 수 있는 edge의 총합 수는 $2|E|$ 이다. 여기에 우선순위 큐 enqueue 비용을 곱하면 $O(2|E| log |V|)$

vertex를 하나 탐색할 때마다, 하나의 edge를 우선순위 큐에서 삭제한다. 이 과정은 모든 vertex에 대해서 실행하므로, $O(|V| log |V|)$

 

 

위 두 식을 더하면 $O((2|E| + |V|) log |V|)$ 가 된다. 일반적으로 $|V| < |E| < |V|^2$ 이므로, 앞의 식은 $O((2|E| + |E|) log |V|)$로 고칠 수 있고, 상수를 제거하면 최종적으로 다음과 같다.

 

$$O(|E| log |V|)$$

4. 코드

boj 1197 - 최소 스패닝 트리: https://www.acmicpc.net/problem/1197

[1197번: 최소 스패닝 트리

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이

www.acmicpc.net](https://www.acmicpc.net/problem/1197)

C++

#include<stdio.h>
#include<queue>
#include<vector>

using namespace std;

struct Node{
    unsigned int node;
    int weight;

    Node(unsigned int n, int w): node(n), weight(w){};

    bool operator<(const Node& n) const{
        return this->weight > n.weight;
    }
};


int main(){
    vector<Node> graph[10001];
    int v, e;
    scanf("%d %d",&v,&e);

    // Input
    for(int i = 0; i < e; i++){
        int a,b,c;
        scanf("%d %d %d", &a, &b, &c);
        graph[a].push_back(Node(b, c));
        graph[b].push_back(Node(a, c));
    }

    // PRIM
    priority_queue<Node> heap;
    bool visited[10001] = {0,};
    int ANS = 0;

    heap.push(Node(1, 0));
    while(!heap.empty()){
        unsigned int node = heap.top().node;
        int weight = heap.top().weight;
        heap.pop();

        if(visited[node]) continue;

        ANS += weight;
        visited[node] = true;
        for(auto next : graph[node]){
            if(!visited[next.node]){
                heap.push(Node(next.node, next.weight));
            }
        }
    }
    printf("%d\n",ANS);
}

RUST

use std::io::{stdin, Read};
use std::cmp::Ordering;
use std::collections::BinaryHeap;

#[derive(Clone, Copy, Eq, PartialEq)]
struct Node{
    node: usize,
    weight: i32,
}

impl Ord for Node{
    fn cmp(&self, other: &Self) -> Ordering{
        other.weight.cmp(&self.weight)
    }
}
impl PartialOrd for Node{
    fn partial_cmp(&self, other:&Self) -> Option<Ordering>{
        Some(self.cmp(other))
    }
}
fn main() {
    let mut input = String::new();
    stdin().read_to_string(&mut input).unwrap();
    let mut input = input.split_ascii_whitespace().flat_map(str::parse::<i32>);

    let v = input.next().unwrap();
    let e = input.next().unwrap();

    let mut graph : Vec<Vec<Node>> = vec![Vec::new(); 10001];

    // Input
    for _i in 0..e{
        let a = input.next().unwrap() as usize;
        let b = input.next().unwrap() as usize;
        let c = input.next().unwrap();

        graph[a].push(Node{node: b, weight: c});
        graph[b].push(Node{node: a, weight: c});
    }

    // PRIM
    let mut heap: BinaryHeap<Node> = BinaryHeap::new();
    let mut visited: [bool;10001] = [false;10001];
    let mut ANS = 0;

    heap.push(Node{node: 1, weight: 0});
    while let Some(Node {node, weight}) = heap.pop(){
        if visited[node] {
            continue;
        }
        ANS += weight;
        visited[node] = true;
        for next in &graph[node]{
            if !visited[next.node]{
                heap.push(Node{node: next.node, weight: next.weight});
            }
        }
    }
    println!("{ANS}");
}