최소 신장 트리(MST): Prim, Kruskal

1. 신장 트리 (spanning tree)

그래프 $ G=${$ V, E $} 에서 $V$의 모든 정점을 포함하면서 순환(cycle)이 존재하지 않는 부분 그래프

어떤 그래프에서 신장 트리가 유일한 건 아니다.

 

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

가중 그래프에서 가중치의 합을 최소로 하는 신장 트리

최소 신장 트리(MST) 알고리즘

• Prim 알고리즘
• Kruskal 알고리즘

 

Prim 알고리즘

입력: 그래프 $G=${$V, E$}
출력: 최소 신장 트리 $G^T = ${$V, T$}
초기값: $T=∅, U=${$s$} ($s ∈V$, 즉 $G$의 임의의 노드)
while ($U ≠V$)
    $u∈U, v∈V-U$ 의 두 정점을 연결하는 모든 연결선 중에서 가장 적은 비용의 연결선 ($u, v$)를 선택한다.
    $T=T∪${($u, v$)}
    $U=U∪${$v$}
    $u ← v$

그리디 알고리즘의 하나이지만, Prim 알고리즘은 모든 그래프에 대해 최적의 해를 구한다.

❓ Greedy algorithm (탐욕 알고리즘)

결정을 할 때마다 최종 결과에 관계 없이 그 순간에서 최선의 선택을 한다.
그 순간의 선택은 그 순간에서 최적의 선택이다 (locally optimal solution).
하지만, 최종의 결과가 최적(global optimal solution)이라는 보장은 없다 .
예) simple coloring algorithm, TSP(travelling salesman problem)

 

증명

연결선 중 비용이 가장 작은 걸 $e$ 로 한다. 즉, $ \overline {GE} $.

$ G_1 $ 은 $ A, B, F, G $ 로 된 그래프, $ G_2 $ 는 $ C, D, E $ 로 된 그래프.

(어렵지만 대충 정리해보자면) MST를 만들어가면서 최소 비용의 연결선인 $e$ 를 더해가면 그 그래프가 결국 MST일 수밖에 없다. 최소 비용의 연결선을 포함해야만 MST가 된다.

• 복잡도 ≤ $V^2$(사실 알고리즘의 복잡도는 어떤 data structure로 어떻게 구현하느냐에 달려있으므로, 좋은 자료구조로 구현하면 $V*logE$) ∴ $O(V^2)$

'''
6 11
0 1 32
0 2 31
0 5 60
0 6 51
1 2 21
2 4 46
2 6 25
3 4 34
3 5 18
4 5 40
4 6 51
'''

def prim1(r, V):
    MST = [0]*(V+1)     # MST 포함여부
    key = [10000]*(V+1) # 가중치의 최대값 이상으로 초기화. key[v]는 v가 MST에 속한 정점과 연결될 때의 가중치
    key[r] = 0          # 시작정점의 key
    for _ in range(V):  # V+1개의 정점 중 V개를 선택
        # MST에 포함되지 않은 정점 중(MST[u]==0), key가 최소인 u 찾기
        u = 0
        minV = 10000
        for i in range(V+1):
            if MST[i]==0 and key[i]<minV:
                u = i
                minV = key[i]
        MST[u] = 1                  # 정점 u를 MST에 추가
        # u에 인접인 v에 대해, MST에 포함되지 않은 정점이면
        for v in range(V+1):
            if MST[v]==0 and adjM[u][v]>0:
                key[v] = min(key[v], adjM[u][v])     # u를 통해 MST에 포함되는 비용과 기존 비용을 비교, 갱신
    return sum(key)         # MST 가중치의 합

def prim2(r, V):
    MST = [0]*(V+1)     # MST 포함여부
    MST[r] = 1
    s = 0
    for _ in range(V):
        u = 0
        minV = 10000
        for i in range(V+1):    # MST에 포함된 정점i와 인접한 정점j 중 MST에 포함되지 않고 가중치가 최소인 정점 u찾기
            if MST[i]==1:
                for j in range(V+1):
                    if adjM[i][j]>0 and MST[j]==0 and minV>adjM[i][j]:
                        u = j
                        minV = adjM[i][j]
        s += minV
        MST[u] = 1
    return s




V, E = map(int, input().split())
adjM = [[0]*(V+1) for _ in range(V+1)]
adjL = [[] for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    adjM[u][v] = w
    adjM[v][u] = w  # 가중치가 있는 무방향 그래프
    adjL[u].append((v, w))
    adjL[v].append((u, w))
print(adjM)
print(adjL)
#print(prim1(0, V))
print(prim2(0, V))

---

Kruskal 알고리즘

입력: 그래프 $G=${$V, E$}
출력: 최소 신장 트리 $G^T=${$V, T$}
초기값: $T=∅$
$E$의 모든 연결선을 비용이 적은 순서대로 정렬한다.
while ($T$의 연결선의 수 < $V$의 정점의 수 $- 1$)
    순서대로 정렬된 $E$의 연결선 중에서 차례대로 ($u, v$)를 선택한다. 이때 ($u, v$)는 $T$에 속한 연결선과 순환을 만들지 않는 것이어야 한다.

• 복잡도: $EV$ (또는 구현에 따라 $ElogE$)

def find_set(x):	# 사이클 테이블
    while x!=rep[x]:
        x = rep[x]
    return x

def union(x, y):
    rep[find_set(y)] = find_set(x)

V, E = map(int, input().split())    # V 마지막 정점, 0~V번 정점. 개수 (V+1)개
edge = []
for _ in range(E):
    u, v, w = map(int, input().split())
    edge.append([w, v, u])
edge.sort()
rep = [i for i in range(V+1)]       # 대표원소 배열
# MST의 간선수 N = 정점 수 - 1
N = V - 1
cnt = 0     # 선택한 edge의 수
total = 0   # MST 가중치의 합
for w, v, u in edge:
    if find_set(v) != find_set(u):
        cnt += 1
        union(u, v)
        total += w
        if cnt == N-1:  # MST 구성이 끝나면
            break
print(total)

사이클 테이블은 다음과 같이 만들 수 있다:

노드 $i$ 와 노드 $j$ 가 연결되어 있고 $i < j$ 라고 할 때, 해당 간선을 MST에 포함시키게 되면, $j$의 사이클 테이블의 값을 $i$의 사이클 테이블의 값으로 만드는 것이다. 즉, $j$의 부모 노드를 $i$의 부모 노드로 설정하는 것이다.

이렇게 하면, 서로 다른 두 노드 사이의 연결선을 MST 에 포함시키기 전에 사이클 테이블을 확인하여, 두 노드의 사이클 테이블 값이 서로 같으면 순환이 생기므로 MST에 포함시키지 않는 식으로 크루스칼 알고리즘을 구현할 수 있다.

💭 참고: 안경잡이 개발자의 '19강. 크루스칼 알고리즘'