23. Minimum Spanning Trees

그래프의 정점을 전부 연결하는 트리를 신장 트리라 한다. 간선에 가중치가 주어졌을 때 가중치의 합을 최소로 하는 트리를 최소 신장 트리라 하며 이를 찾는 문제를 최소 신장 트리 문제라 한다. 이는 탐욕적 알고리즘인 크루스칼의 알고리즘이나 프림의 알고리즘으로 구현될 수 있다. O(E \lg V)의 쉬운 구현이 있으며 피보나치 힙을 사용하면 프림의 알고리즘은 O(E + V \lg V)에 구현할 수 있다.

23.1. Growing a minimum spanning tree

가중치가 주어진 비방향 연결그래프가 있다고 하자. 이 때 최소 신장 트리를 찾는 탐욕적 알고리즘은 다음을 불변조건으로 한다: 각 반복 이전에, 알고리즘이 만들어나가는 간선의 집합은 어떠한 최소 신장 트리의 부분집합이다. 이 때 추가했을 때 이 불변조건을 깨지 않는 간선을 안전 간선이라 한다. 이를 활용하면 최소 신장 트리의 유사코드는 다음과 같다.

GENERIC-MST(G, w)
A = Φ
while A does not form a spanning tree
    find an edge (u, v) that is safe for A
    A = A ∪ {(u, v)}
return A

몇 가지 정의를 하자. 비방향그래프의 절단은 해당 그래프의 분할이다. 어떤 간선이 해당 절단의 한 부분과 다른 부분을 연결할 경우 해당 간선이 이 절단을 교차한다고 한다. 어떤 절단을 교차하지 않는 간선의 집합에 대해 이 절단이 이 집합을 존중한다고 한다. 절단을 교차하는 간선 중 최소 가중치의 간선을 가벼운 간선이라 한다. 이 때 다음이 성립한다.

Theorem. G = (V, E)가 실수 가중치가 주어진 비방향 연결그래프라 하자. A가 G의 최소 신장 트리의 부분집합인 간선들의 집합이고 G의 절단 (S, V – S)이 A를 존중한다면, 이 절단에 대한 가벼운 간선은 A에 대한 안전 간선이다.

이는 GENERIC-MST의 불변 조건을 보장한다.

Corollary. G = (V, E)가 실수 가중치가 주어진 비방향 연결그래프라 하자. A가 G의 최소 신장 트리의 부분집합인 간선들의 집합이고 C가 (V, A) 내의 연결요소라면, C에서 (V, A) 내 다른 연결요소로의 간선 중 가벼운 간선은 A에 대한 안전 간선이다.

23.2. The algorithms of Kruskal and Prim

크루스칼의 알고리즘과 프림의 알고리즘을 알아보자.

Kruskal’s algorithm

크루스칼의 알고리즘은 다음과 같다.

MST-KRUSKAL(G, w)
A = Φ
for each vertex v ∈ G.V
    MAKE-SET(v)
sort the edges of G.E into nondecreasing order by weight w
for each edge (u, v) ∈ G.E, taken in nondecreasing order by weight
    if FIND-SET(u) ≠ FIND-SET(v)
        A = A ∪ {(u, v)}
        UNION(u, v)
return A

이 알고리즘의 복잡도는 O(E \lg V)이다.

Prim’s algorithm

프림의 알고리즘은 다음과 같다.

MST-PRIM(G, w, r)
for each u ∈ G.V
    u.key = ∞
    u.π = NIL
r.key = 0
Q = G.V
while Q ≠ Φ
    u = EXTRACT-MIN(Q)
    for each v ∈ G.Adj[u]
        if v ∈ Q and w(u, v) < v.key
            v.π = u
            v.key = w(u, v)

이 알고리즘의 복잡도는 O(E \lg V)이다. Q를 피보나치 힙을 이용해 구현한다면 수행 시간은 O(E + V \lg V)가 된다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중