JArchive 프로그래밍 일기

최소 스패닝 트리 (MST, Minimum cost spanning tree)

스패닝 트리 (spanning tree)

그래프에 있는 모든 정점을 포함하는 부분 그래프

N개의 정점(vertex)와 N-1개의 간선(edge)으로 구성

간선들이 트리 형태이며, 간선들이 모든 정점들을 연결해야 한다.

간선이 트리 형태여야 한다?

선택된 간선들이 사이클(cycle)을 이루지 않는다는 의미

연결 그래프에서 1개 이상의 스패닝 트리를 얻을 수 있다.

DFS, BFS로 얻을 수 있는 스패닝 트리

연결 그래프에서, DFS나 BFS는 암묵적으로 그래프 G의 간선(edge)을 두 개의 집합으로 분리한다.

• T : 스패닝 트리의 edge 집합으로 사용되거나 search 도중에 방문
• N : 남아있는 edge의 집합

아래 그림에서 V(정점)는 8개, E(간선)은 7개이다.

(만약 edge가 vertext의 개수와 같아지면 cycle이 생긴다. )

(a) DFS spanning tree

아직 방문하지 않은 정점으로 향하는 간선이 있으면 그 간선을 무조건 따라간다.

가능한 한 그래프 안으로 '깊이' 간선을 따라가며, 막힌 정점에 도달하면 뒤로 돌아간다.

(b) BFS spanning tree

각 정점을 방문할 때 마다 모든 인접 정점을 검사하므로 V0에서 V1과 V2 쪽으로 순차적으로 두 간선을 방문한다.

최소 스패닝 트리 (minimum cost spanning tree)

가중치 그래프의 스패닝 트리 중, 가중치의 합이 가장 작은 트리

즉, 그래프의 연결성은 유지하되 가장 '저렴한' 그래프

정점이 N개라면, 간선은 N-1개만을 포함한다.

사이클을 만드는 간선은 선택하지 않는다.

최소 스패닝 트리 알고리즘

크루스칼(Kruskal), 프림(Prim), 솔린(Sollin) 알고리즘이 대표적이다. 세 알고리즘 모두 탐욕 알고리즘이다.

탐욕 알고리즘(greedy method)

현재 상황에서 최선의 선택을 한다.

크루스칼과 프림은 상호 배타적 조합(Disjoint Set)을 기본 자료구조로 쓴다.

1. 크루스칼

모든 간선(edge)을 가중치의 오름차순으로 정렬한다.

가중치가 가장 작은 edge를 선택하여 스패닝 트리에 하나씩 추가해 간다.

이 때, 추가하면 사이클이 생기는 간선을 확인하여 제외시킨다.

이렇게 모든 간선을 한 번씩 검사하고 난 뒤 종료한다.

사이클이 발생했는지 판단하는 기준

Union-Find (유니온 파인드) 자료구조를 이용하여 O(1)에 확인 가능

트리에 추가된 정점, 그렇지 않은 정점. 이렇게 두 집합으로 정점들이 나뉜다.

사이클이 생기는 경우, 간선의 양 끝 정점은 같은 컴포넌트(집합)에 속한다.

두 정점이 주어 졌을 때, 이들이 같은 집합에 속하는지 확인(Find)하고,

다른 집합에 속하는 정점이라면 합치는 연산(Union)을 빠르게 지원한다.

크루스칼 알고리즘 탐색 예시

간선 가중치를 정렬한 결과 10, 12, 14, 16, 18, 22, 24, 25, 28

그림 (f) 와 (g) 를 눈여겨보자.

(f) 10, 12, 14, 16을 추가한 트리

(g) 18을 추가하면 사이클이 발생하므로 18을 제외시키고, 22를 추가한다.

2. 프림

하나의 정점으로 구성된 트리에서 시작한다.

여기에 간선을 하나씩 추가하며 스패닝 트리가 될 때까지 키워 간다.

이미 만들어진 트리에 인접한 간선만 고려한다.

(인접한 간선만 고려한다는것 빼고는 크루스칼과 완전히 똑같다. )

시작 정점으로 부터 인접한 정점을 Priority Queue(pq)에 저장하는데, 이때 인접 정점과 간선의 가중치를 함께 저장한다.

프림 알고리즘 탐색 예시

크루스칼 vs 프림

문제 : 최소 스패닝 트리

백준 1197번 최소 스패닝 트리

[참고]

유니온 파인드 개념

[출처]

크루스칼 알고리즘 그림

프림 알고리즘 그림