최소 신장 트리 개념

최소 신장 트리

가중그래프

각 간선이 무게라 불리는 수치값을 가진다.

최소 신장 트리

신장 부그래프란 그래프 G의 모든 정점들을 포함하는 부그래프를 말하며 신장트리는 (자유) 트리인 신장 부그래프를 말한다. 가중그래프 G의 최소신장트리MST는 G의 신장트리 가운데 간선 무게의 합이 최소인 것을 말한다.

최소 신장 트리의 속성

싸이클 속성

T를 가중그래프 G의 최소신장트리라 하자. e를 T에 존재하지 않는 G의 간선으로 e를 T에 추가하여 형성된 싸이클을 C로 가정하자. 그러면 C의 모든 간선 f에 대해 weight(f)<= weight(e)이다.

• 싸이클에서 가장 큰 숫자를 안써야 최소 신장 트리가 되기 때문이다.

  분할 속성

  G의 정점들을 두 개의 부분집합 U와 V로 분할한다고 하자. e를 분할을 가로지르는 최소 무게의 간선이라고 하자. 그러면 간선 e를 포함하는 G의 최소신장트리가 반드시 존재한다.
• 분할할 땐 가장 작은 숫자를 써야 최소 신장 트리가 되기 때문이다.

  탐욕법

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

  최소 신장트리 알고리즘

  prime-Jarnik 알고리즘

  임의의 정점 s를 택하여 s로부터 시작하여 정점들을 배낭에 넣어가며 배낭안에서 MST를 키워나가는 것.
• 거리: d(v)
• 위치자: 우선순위 큐에서의 v의 위치
• 부모: p(v), MST T(루트)에서 v의 부모를 향한 간선
• Q.replaceKey(e,k): 원수e의 키를 k로 변경하고 우선순위 큐 Q내의 e의 위치를 갱신

  Alg Prime-JarnikMST(G)

1. for each v to G.vertices(){
   d(v) = INF
   p(v) = NULL
   }

2. s = a vertex of G

3. d(s) = 0

4. Q = a priority queue contaning all the vertices of G using d labels as keys

5. while(!Q.isEmpty){
   u = Q.removeMin()
   for each e to G.incidentEdges(u)

    z = G.opposite(u,e)
    if((z in Q)&(w(u,z)<d(z))){
        d(z) = w(u,z)
        p(z) = e
        Q.replaceKey(z,w(u,z))
    }

   }

6. 모든 정점의 거리를 무한으로 두고, 부모도 NULL로 둔다.

7. 아무 정점이나 잡아서 그 거리를 0으로 두고 모든 정점들을 큐에 넣는다.

8. 큐에서 가장 작은 값을 꺼내서 거기서 갈 수 있는 모든 정점들 중 큐에 존재하고, 거리가 갱신하는 것 보다 크다면 거리를 새롭게 갱신하고 큐를 재조정한다.

9. 큐가 빌때 까지 3번을 반복한다.

알고리즘 분석

incidentEdges는 각 정점에 대해 한번 씩 호출되고, 라벨 관련 작업은 O(deg(z))가 소모된다. Q를 힙으로 구현할 경우 삽입과 삭제는 각각 O(log n)시간이 소요된다. Q 내의 정점 w의 키는 최대 deg(w)번 변경된다. 각 키 변경은 O(log n)시간이 소요된다.
그러므로 알고리즘은 O((n+m)logn) 시간에 수행한다. 단순 연결 그래프에서 n = O(m)이므로 이를 O(mlog n)으로 단순화할 수 있따.

Kruskal 알고리즘

각 정점을 각각의 배낭으로 두고, 두 배낭을 합칠 때 가장 작은 간선을 선택하는 식으로 키워가는 것이다. G의 정점 수 n보다 하나 작은 수의 간선을 배낭에 포함할 때까지 반복한다. 반복이 완료되면 MST T를 포함하는 한개의 배낭만 남는다.

Alg KurskalMST(G)

1. for each v to G.vertices()
    define a Sack(v) = {v}
2. Q = a priority queue contaning all the edges of G using weights as keys
3. T = NULL
4. while(T has fewer than n-1 edges){
    (u,v) = Q.removeMin()
    if(Sack(u)!= Sack(v)){
        Add edge(u,v) to T
        Merge Sack(u) and Sack(v)
    }
}
5. return T

1. 모든 정점을 각각의 sack로 둔다.
2. Q에 전부 넣고 T는 NULL로 둔다.
3. Q에서 최소를 뽑고 둘이 다른 sack이면 u,v를 T에 추가하고, sack를 합친다.
4. T의 edge가 n-1보다 작은 동안 3을 반복한다.

BaruvKa 알고리즘

Alg BaruvkaMST(G)

1. T = V
2. while( T has fewer than n-1 edges){
    for each connected component Ci in T{
        Let edge e be the smallest-weight edge from Ci to anothor component in T
        if(e is not already in T)
            Add edge e to T
    }
}
3. return T

MST 알고리즘 비교

알고리즘	주요 전략	실행시간	외부 데이터 구조
PrimeJamik	탐욕법	$O(mlogn)$	정점들을 저장하기 위한 우선순위 큐
Kruskal	탐욕법	$O(mlogn)$	간선들을 저장하기 위한 우선순위 큐 배낭들을 구현하기 위한 분리집합
PrimeJamik	탐욕법	$O(mlogn)$	정점들을 저장하기 위한 우선순위 큐