최소 신장 트리

모든 정점을 잇는 가장 싼 방법. 신장 트리(spanning tree)는 그래프의 모든 정점을 최소한의 간선으로 연결한 부분 그래프이고, 그중 가중치 합이 가장 작은 것이 최소 신장 트리다.

정점이 N개면 간선은 정확히 N-1개다. 모두 연결되어 있으면서 사이클이 없는 것이 트리의 정의이기 때문이다.

모양은 달라도 같은 비용

같은 그래프에서 크루스칼과 프림이 서로 다른 모양의 트리를 내놓을 수 있다. 하지만 가중치의 합은 언제나 같다. 최소 신장 트리는 모양이 아니라 비용으로 정의되기 때문이다.

간선을 넣을지 말지는 사이클이 생기는지로 정한다. 이미 트리에 있는 두 정점을 이으면 사이클이 생기고, 트리에 없던 정점이 새로 들어오는 형태면 사이클이 안 생긴다.

크루스칼

모든 간선을 가중치 오름차순으로 정렬한 뒤, 싼 것부터 하나씩 보면서 그 간선의 양 끝이 아직 다른 그룹이면 채택하고 두 그룹을 합친다. 같은 그룹이면 건너뛴다. 넣으면 사이클이 생기기 때문이다.

for E in edge[]
    u, v = E
    if find(u) != find(v)
        mst.push(E)
        union(u, v)

같은 그룹인지 판단하는 데 유니온 파인드가 쓰인다. 정렬에 O(E log E), 간선마다 union-find에 O(log N)이 들어 O(E log N)이니 합치면 정렬이 지배해서 O(E log E)다.

프림

아무 정점에서 시작해서, 지금까지 만든 트리에 가장 싸게 붙일 수 있는 정점을 골라 추가하는 일을 모든 정점이 들어올 때까지 반복한다. 우선순위 큐를 쓰면 O(E log V), 단순 반복이면 O(V²)다.

프림은 사이클 걱정을 할 필요가 없다. 항상 트리에 없는 정점만 후보로 보기 때문에 사이클이 생길 수가 없다. 크루스칼은 전체에서 싼 간선을 고르므로 매번 확인해야 한다.

프림과 다익스트라의 두 줄 차이

프림과 다익스트라는 거의 같은 알고리즘이다. 두 줄만 다르고, 그 두 줄은 dist 배열이 무엇을 뜻하느냐에서 온다.

다익스트라는 시작점부터의 누적 거리를 재고, 프림은 붙이는 간선 하나의 값만 본다. 목적이 다르니 재는 것도 다르다.

관련

• 유니온 파인드
• 다익스트라
• 그래프

출처

• 코드트리 그래프 탐색 - MST, Kruskal, Prim