[알고리즘] 최소 비용 신장 트리 (MST)

🎄 최소 비용 신장 트리 (MST)

전체 그래프에서 총합이 최소인 신장 트리

• 신장 트리?

1. 모든 정점을 연결
2. 사이클이 존재하지 않는 부분 그래프
   • 간선의 개수 : N -1 개
3. 한 그래프에서 여러 개의 신장 트리가 나올 수 있다

• MST?

  Minimum Spanning Tree : 전체의 가중치 값 중 최소인 트리

---

Prim 알고리즘

하나의 정점에서 연결된 간선들 중에 하나씩 선택하며 MST를 만들어가는 방식

1. 임의의 정점 하나 선택
2. 선택한 정점과 인접 정점들 중 최소 비용의 간선이 존재하는 정점을 선택
3. 모든 정점이 선택될 때까지 반복

• 서로소인 2개의 집합(2 disjoint-sets) 정보를 유지
  - 트리 정점(tree vertices): MST를 만들기 위해 선택된 정점들
  • 비트리 정점(nontree vertices): 선택되지 않은 정점들

우선순위 큐 - 힙 구현

import heapq # 힙 구조 라이브러리

def prim(start):
    heap = []
    # 자동으로 내부적인 우선순위에 따라 정렬하여 넣어줌
    # 기본 default : 오름차순
    # 내림차순 ? 음수로 heappush한 후 음수로 heappop
    heapq.heappush(heap, 3)
    heapq.heappush(heap, 1)
    heapq.heappush(heap, 2)

    print(heapq.heappop(heap))
    print(heapq.heappop(heap))
    print(heapq.heappop(heap))
prim(0)
# 1
# 2
# 3 

prim 알고리즘 구현

<입력값>
7 10
0 1 32
0 2 31
0 5 60
1 2 21
2 4 46
2 6 25
3 4 34
3 5 18
4 5 40
4 6 51

import heapq

def prim(start):
    heap = []
    # MST 에 포함되었는 지 여부
    MST = [0] * V

    # 가중치, 정점 정보
    heapq.heappush(heap, (0, start))
    # 누적합 저장
    sum_weight = 0

    while heap:
        # 가장 적은 가중치를 가진 정점을 꺼냄
        weight, v = heapq.heappop(heap)

        # 이미 방문한 노드라면 pass
        if MST[v]:
            continue

        # 방문 체크
        MST[v] = 1

        # 누적합 추가
        sum_weight += weight

        # 갈 수 있는 노드들을 체크
        for next in range(V):
            # 갈 수 없거나 이미 방문했다면 pass
            if graph[v][next] == 0 or MST[next]:
                continue

            heapq.heappush(heap, (graph[v][next], next))

    return sum_weight


V, E = map(int, input().split())
# 인접행렬
graph = [[0] * V for _ in range(V)]

for _ in range(E):
    f, t, w = map(int, input().split())
    graph[f][t] = w
    graph[t][f] = w  # 무방향 그래프

result = prim(0)
print(f'최소 비용 = {result}')

---

Kruskal 알고리즘

모든 간선들 중 비용이 가장 적은 걸 우선으로 선택

v, e = map(int, input().split())
edge = []
for _ in range(e):
    f, t, w = map(int, input().split())
    edge.append([f, t, w])
# w 를 기준으로 정렬
edge.sort(key=lambda x: x[2])

# 사이클 발생 여부를 union find 로 해결
parents = [i for i in range(v)]

def find_set(x):
    if parents[x] == x:
        return  x
    return  find_set(parents[x])


def union(x, y):
    x = find_set(x)
    y = find_set(y)

    if x == y:
        return

    if x < y:
        parents[y] = x
    else:
        parents[x] = y

# 현재 방문한 정점 수
cnt = 0
sum_weight = 0
# edge를 정렬했기에 선택할 때 가장 적은 수부터 고르게 된다
for f, t, w in edge:
    # 싸이클이 발생하지 않는다면 == 두 개의 대표자가 서로 다르다면
    if find_set(f) != find_set(t):
        cnt += 1
        sum_weight += w
        union(f, t) # 같은 집합으로 묶어준다 (연결)
        # MST 구성이 끝나면
        if cnt == v:
            break

print(f'최소 비용 = {sum_weight}')