16. 최소신장트리 (Minimum Spanning Tree)

신장 트리는 그래프의 모든 노드를 방문하고, 사이클이 없는 그래프이다.
최소 신장 트리는 어떤 가중 그래프에서 가중치의 합이 최소가 되는 신장 트리이다.

최소 신장 트리는 아래 두 가지 속성을 갖는다.

사이클 속성

$T$를 가중그래프 G의 최소신장트리라 하자. $e$를 $T$에 존재하지 않는 $G$의 간선으로, $C$를 $e$를 $T$에 추가하여 형성된 사이클로 가정할 때, $C$의 모든 간선 $f$에 대해 $\text{weight}(f)\leq \text{weight}(e)$가 성립한다.

왜냐하면, 만약 $\text{weight}(f)\geq \text{weight}(e)$라면, $f$를 $e$로 대체함으로써 가중치 합이 더 작은 신장트리를 얻을 수 있기 때문이다.

분할 속성

$G$의 노드들을 두 개의 부분집합 $U, V$로 분할한다고 하자. $e$를 분할을 가로지르는 최소 무게의 간선이라고 하자. 간선 $e$를 포함하는 $G$의 최소신장트리가 반드시 존재한다.

탐욕법

탐욕법은 일반적인 알고리즘 설계 기법 가운데 하나로, 다음 요소에 기초하여 설계한다.

• 구성: 다양한 선택, 모음, 또는 찾아야 할 값들
• 목표: 구성에 하당된 정수가 존재하며, 이를 최대화 또는 최소화해야 하는 상황

탐욕적 선택 속성을 가진 문제에 적용할 경우 가장 잘 맞는다. 탐욕적 선택 속성이란, 매 순간 최선의 선택을 통해 전체 최적해를 항상 찾을 수 있는 속성이다.

Prim-Jarnik 알고리즘

탐욕법을 이용한 알고리즘이다.

임의의 정점 $s$를 택하여, $s$로부터 시작하여 정점들을 배낭에 넣어가며 배낭 안에서 MST $T$를 키워 나간다. $s$는 $T$의 루트가 된다.

각 정점 $v$에 라벨 $d(v)$를 정의하는데, 이는 배낭 내부의 정점과 외부의 정점을 연결하는 간선의 가중치이다.

1. 반복의 각 회전에서 배낭 밖의 정점들 가운데 최소 $d(z)$ 라벨을 가진 정점 $z$를 배낭에 넣는다.
2. z에 인접한 정점들의 라벨을 갱신한다.

각 정점은 우선순위 큐에 한번 삽입되고 한번 삭제되므로, $O(\log n)$시간이 소요되고, 각 노드의 키는 최대 $\text{deg}(w)$번 변경되는데, 이는 각각 $O(\log n)$ 시간 소요된다.

즉, 그래프가 인접리스트 구조일 때, 알고리즘은 $O((n+m)\log n)$시간에 수행된다.

def primMST(G, s): # s는 루트가 될 노드
    for v in G.vertices:
        d(v) = np.inf
        p(v) = null # MST에서 v의 부모를 향한 간선
    d(s) = 0
    Q = priorityQueue()
    Q.init(G) # 모든 노드가 들어있고, d를 라벨로 하는 우선순위 큐
    while not Q.isEmpty():
        u = Q.removeMin()
        for e in G.incidentEdges(u):
            z = G.opposite(u, e)
            if z in Q and w(u, z) < d(z): # z가 아직 MST 밖에 있고, u에서 z로 가는게 d(z)보다 좋을 때
                d(z) = w(u, z)
                p(z) = e
                Q.replaceKey(z, w(u,z))

Kruskal 알고리즘

탐욕법을 이용한 알고리즘이다.

시작할 때, 모든 노드를 각각의 독자적인 배낭에 넣는다. 배낭 밖의 간선들을 우선순위 큐에 넣는다. (키는 가중치)

두 개의 다른 배낭 속에 양 끝점을 가진 최소 가중치 간선을 $T$에 포함하고, 두 배낭을 합친다. 반복을 마치면 MST가 담긴 배낭 하나만 남는다.

우선순위 큐 초기화에 상향식 힙 생성을 통해서는 $O(m)$, 일반적인 방식으로는 $O(m \log m)$시간이 소요되고, 반복의 각 회전에서 최소 무게 간선을 $O(\log m)$시간에 삭제 가능한데, 각 배낭을 위한 분리집합을 리스트로 구현하면 각 배낭을 연결하는 검사에 $O(1)$시간이 걸린다.

그러므로 크루스칼 알고리즘은 $O((n+m)\log n)$시간에 수행된다.

Baruvka 알고리즘

크루스칼이나 프림 알고리즘과 달리 우선순위 큐를 사용하지 않는다. 크루스칼 알고리즘과 마찬가지로 모든 노드를 각각의 배낭에 넣고 시작한다.

기존의 알고리즘들과 달리, 한 회전에 여러개의 간선을 취하여 여러 개의 배낭을 동시에 키워나간다.

def Maruvka(G):
    T = G.vertices()
    while len(T.edges) < len(G.vertices)-1:
        for e in nextEdge(T): # T안에 있는 연결 요소 Ci로부터 다른 요소까지의 간선 중 가장 작은 가중치를 가진 간선
            if not e in T(edges):
                T.append(e)
                
    return T

MST 알고리즘 비교

알고리즘	주요전략	수행 시간	외부 데이터구조
Prim-Jarnik	탐욕	$O(m \log n)$	정점들을 저장하기 위한 우선순위 큐
Kruskal		$O(m \log n)$	간선들을 저장하기 위한 우선순위 큐 배낭들을 구현하기 위한 분리집합 (리스트로 구현 가능)
Baruvka		$O(m \log n)$	연결요소를 표현하기 위한데이터구조 필요