MST 최소 신장 트리

Python

MST 최소 신장 트리

물리 water lee 2024. 10. 9. 20:58

최소 비용 신장 트리(Minimum Spanning Tree, MST)는

연결된 가중 그래프에서 모든 정점을 포함하고, 간선의 총 가중치가 최소인 트리를 의미합니다.

예를 들어, 아주 큰 놀이터를 설계하고 있다고 생각해봅시다.
이 놀이터에는 여러 개의 놀이기구가 있는데, 이 놀이기구들을 "모두 연결하는 길"을 만들어야 합니다.
길을 만들 때는 "비용"이 드니까, 가능한 "적은 비용"으로 모든 놀이기구를 연결하는 것이 목표입니다.

어떻게 하면 좋을까요?

놀이기구는 점으로 생각하고, 길은 선으로 생각해봅시다.
모든 놀이기구를 연결하는 선을 그려야 해요.

그리고 가장 적은 비용으로 모든 놀이기구를 연결해야 해요.
즉, 길의 총 길이가 최소가 되도록 해야 하는 거죠.

길을 만들 때, 같은 곳을 두 번 이상 돌아오지 않도록 해야합니다.
즉, 원 모양으로 돌지 않아야 해요.

또 다른 예시를 들어볼까요?

서울에서 부산으로 가는 투어를 기획한다고 가정해봅시다.
하지만, 단순히 서울에서 부산으로 곧장 가는 것이 아니라 중간에 여러 도시를 거치며 여행을 하는 것이죠.
예를 들어, 대전, 대구, 울산 등 여러 도시에 들러가며 투어를 즐길 계획입니다.

이때, 목표는 비용을 최소화하면서 모든 도시에 한 번씩 들러 서울에서 출발해 부산까지 도착하는 것입니다.
각 도시를 연결하는 교통비나 이동 거리가 다 다르기 때문에, 어떻게 하면 최소한의 비용으로 서울부터 부산까지 모든 도시를 연결할 수 있을지 고민하게 됩니다.

어떻게 하면 좋을까요?

각 도시는 정점으로 생각할 수 있고, 도시를 연결하는 이동 경로(길이나 교통 수단)는 간선으로 볼 수 있죠.
이 간선에는 이동 거리나 비용이 가중치로 붙게 됩니다.

그리고 '모든 도시를 연결하는 가장 작은 비용의 경로'를 찾는 것이 우리의 목표입니다.
모든 도시를 연결하되, 불필요하게 다시 돌아오는 경로나 순환 경로를 없애고, 한 번만 지나가며 최소 비용을 찾는 것이죠.

이러한 루트를 찾는 것이 바로 "최소 비용 신장 트리" 알고리즘입니다.

이론적으로 이야기해봅시다.

📁 신장 Spanning

여기서 신장이란 📌그래프의 모든 정점을 포함하면서도 📌사이클(순환)이 없는 연결된 구조를 의미합니다.

쉽게 말해, 그래프 내에 모든 정점을 한 번씩 연결하는데, 불필요한 간선을 없애고, 사이클이 생기지 않도록하는 것이 신장 트리입니다.

최소 비용이란 모든 가능한 신장 트리 중에서 간선의 총 가중치가 가장 적다는 것을 뜻합니다.

문득 왜 사이클이 없어야 할까? 생각이 들었습니다.
출근길을 생각해 볼까요,,?!

출근할 때, 집에서 나와 역까지 가는데, 집에 놓고 온 물건이 생각나서 다시 돌아가야 한다고 상상해보세요.
이렇게 되면 시간이 더 걸리고, 불필요한 에너지를 쓰게 됩니다.
처음부터 필요한 물건을 챙겼다면, 돌아가지 않아도 됐을 텐데요.

즉, 최소 비용으로 갈 수 있는 문제점을 해결하기 위해서는 같은 곳을 한 번 더 방문하게 되는 것은 비효율적입니다.
비용이 느는 거죠.
그래서 사이클이 없어야 합니다.

📁 신장 트리

N개의 정점으로 이루어진 무방향 그래프에서 N개의 정점과 N-1개의 간선으로 이루어진 트리
- 모든 정점을 연결
- 트리(계층적, 사이클(순환)이 없음)
전체 그래프에서 신장 트리는 반드시 하나인가? NO

📁 최소 비용 신장 트리 Minimum Spanning Tree

무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장트리

✏️ 최소 비용 신장 트리의 특징

모든 정점을 포함한다.
- 신장 트리는 그래프의 모든 정점을 포함하면서도 사이클이 없는 연결 그래프이다.
사이클이 없다
- 트리 구조의 특성상 사이클이 없다.
최소 가중치
- 선택된 간선의 총 가중치가 최소

✏️ 알고리즘

MST를 찾기 위한 대표적인 알고리즘에는 두 가지 방식이 있습니다.

프림 알고리즘(Prim's Algorithm)과 크루스칼 알고리즘(Kruskal's Algorithm)

두 알고리즘은 "Greedy" 방식으로 접근하며, 항상 가장 작은 것부터 선택합니다.

위에서 설명한 놀이기구 예시를 생각해봅시다.

임의의 놀이기구에서 시작하여 가장 가까운 놀이기구로 계속 연결해 나가는 방법이 있을것이며
모든 가능한 길을 길이에 따라 정렬한 다음에, 가장 짧은 길부터 하나씩 선택해서 연결할 수 있습니다.

프림 알고리즘의 경우 전자, 크루스칼 알고리즘은 후자 입니다.

두 알고리즘을 비교하자면 다음과 같습니다.

프림 알고리즘
- 시작 정점에서 출발해, 인접한 정점 중 가장 적은 비용의 간선을 선택하며 MST를 확장해가는 방식입니다.
- 탐색 과정에서 비용이 더 적게 들 수 있습니다.
- "정점"을 기준으로 생각 + 최소부터 시작
크루스칼 알고리즘
- 간선을 비용 순으로 정렬한 후, 사이클을 만들지 않도록 하나씩 선택해나가는 방식입니다.
- "간선"을 기준으로 생각 + 최소부터 시작 + 사이클을 만들지 않도록 하기

보통 구현이 어렵기 때문에 '그래프'나 '인접 리스트'로 표현하는 것을 지향합니다.

📁 프림 알고리즘 Prim's Algorithm

동작 원리

초기화 : 임의의 정점에서 시작하여 MST를 구축하기 위한 초기 트리를 설정합니다. 이 정점은 MST의 첫 번째 정점으로 간주됩니다.
간선 선택: 현재 MST와 연결된 간선 중에서 가중치가 가장 작은 간선을 선택합니다.
- 우선순위 큐 활용하여 가장 낮은 가중치를 가진 간선을 꺼냄
정점 추가: 선택된 간선의 다른 정점을 MST에 추가하고, 이 정점과 연결된 간선을 고려하여 MST를 확장합니다.
- 만약, 해당 간선이 연결하는 정점이 MST에 포함되어 있다면 무시하고, 다음 간선을 선택함
- 새로 추가된 정점과 인접한 모든 간선이 우선순위 큐에 삽입함.
반복: 모든 정점이 MST에 포함될 때까지 2번, 3번 단계를 반복합니다.

예시

정점 1에서 시작했을 때
- 가장 가까운 정점: 3
- (1, 3) 간선이 MST의 일부가 됨
그다음으로, 1번과 3번 정점에 연결된 간선 중에서 (아직 MST에 포함되지 않은) 가장 작은 간선을 선택
- 2(28), 4(26), 5(14) 중 5가 가장 가까운 정점
- 이제 부분적으로 구성된 트리는 (1, 3)과 (3, 5) 두 개의 간선으로 이루어짐
1번, 3번, 5번 정점에 연결된 모든 간선 중에서 가중치가 가장 작은 간선은 (5, 4)

(1-3)-(3-5)-(5-4)
- (4-6)-(6-7)-(7-2) : 18+22+24 ✅
- (4-2)-(2-7)-(7-6) : 20+24+22

슈도코드

초기화
1. 시작 정점 선택: 임의의 시작 정점 $ s $를 선택합니다.
2. 배열 초기화:
   - 모든 정점 $ i $에 대해, $ \text{near}[i] $를 $ s $로 설정합니다.
   - $ \text{dist}[i] $를 시작 정점 $ s $와의 가중치 $ w_{si} $로 설정합니다.
3. 집합 초기화:
   - $ V_T $: 현재까지 MST에 포함된 정점 집합으로, 처음에는 $ \{s\} $입니다.
   - $ E_T $: 현재까지 MST에 포함된 간선 집합으로, 처음에는 비어 있습니다.

반복
1. 정점 선택: 아직 트리에 포함되지 않은 정점 중에서, 가장 작은 $ \text{dist}(u) $ 값을 가진 정점 $ u $를 선택합니다.
2. 연결 확인: 만약 $ \text{dist}[u] $가 무한대라면, 그래프가 연결되지 않았음을 의미하고 알고리즘을 종료합니다.
3. 간선 추가: 선택한 정점과 그에 가장 가까운 정점을 연결하는 간선을 MST에 추가합니다.
4. 정점 추가: 선택한 정점을 MST의 정점 집합에 추가합니다.
5. 배열 업데이트:
   - 모든 남은 정점에 대해, 새로 추가된 정점과의 거리를 계산하고, 더 짧은 경우 배열을 업데이트합니다.

이 과정은 모든 정점이 트리에 포함될 때까지 반복됩니다. 이 알고리즘은 Prim's 알고리즘과 유사하며, Greedy 접근 방식을 사용하여 최소 비용으로 모든 정점을 연결합니다.

백준 문제 https://www.acmicpc.net/problem/21924

import heapq

# 최소 비용 신장 트리의 경우 cost가 먼저 들어옴

def prim(graph, n):
    # 최소 비용
    mst_cost = 0
    visited = [False] * (n+1)
    pq = [(0, 1)] # cost, node  # 시작점의 가중치는 0, 1번 노드부터 시작

    while pq:
        cost, node = heapq.heappop(pq)

        # 이미 방문한 지점이면 통과
        if visited[node]:
            continue
        
        # 처음 방문한 곳
        # 방문처리하기
        visited[node] = True
        # 비용 구하기
        mst_cost += cost

        # 다음 인접 노드 중 방문하지 않은 곳 탐색
        for next_node, next_cost in graph[node]:
            if not visited[next_node]:
                # 추가
                heapq.heappush(pq, (next_cost, next_node))
    
    if all(visited[1:]):
        return mst_cost
    else:
        return -1


# 건물의 개수, 도로의 개수
N, M = map(int, input().split())

# 인접리스트 만들기
graph = [[] for _ in range(N + 1)]


total_cost = 0
# 건물의 번호 a, b와 두 건물 사이 도로를 만들 때 드는 비용 c
for _ in range(M):
    start, to, cost = map(int, input().split())
    graph[start].append((to, cost))  # 연결된 노드와 비용(가중치)
    graph[to].append((start, cost))  # 무방향 그래프이기 때문
    total_cost += cost  # 도로 다 설치할 때 드는 비용


min_cost = prim(graph, N)
if min_cost == -1:
    print(-1)
else: 
    # 얼마나 절약 되는지 계산하기
    print(total_cost - min_cost)

프림 함수를 설명해보자면

mst_cost : 최소 신장 트리의 총 비용을 저장하는 변수
각 노드의 방문 여부를 확인해야 하기 때문에 visited를 리스트로 생성(이 문제에서는 건물을 1부터 시작함)
pq : 우선순위 큐, (비용, 노드) 튜플을 저장합니다.
알고리즘은 1번 노드에서 시작하여 가장 낮은 비용의 간선을 선택하며 진행됩니다(보통 1번 부터 시작함)
1. 프림 알고리즘에서는 시작 노드의 선택이 최종 결과에 영향을 미치지 않게 됩니다.(최소값의 유일성)
2. 더보기
  A-B : 2, B-C : 1, C-A : 3
  이라고 가정했을 때
  A-B-C : 2+1
  B-C ➡️ 최소 신장 트리 구성을 못함
  C-B-A : 1+2
  두 MST의 구조는 다르지만, 총 가중치는 동일하다는 점을 알 수 있습니다.
  참고자료 : https://www.geeksforgeeks.org/properties-of-minimum-spanning-tree-mst/
모든 노드를 방문했다면, 'mst_cost'를 반환하고, 그렇지 않으면 -1을 반환합니다.

📁 크루스칼 알고리즘 Kruskal Algorithm

크루스칼 알고리즘은 간선을 하나씩 선택해서 MST를 찾는 알고리즘입니다.
최초, 모든 간선을 가중치에 따라 오름차순으로 정렬하고, 가중치가 가장 낮은 간선부터 선택하면서 MST를 확장하는 방식입니다.

크루스칼 알고리즘은 특히 간선의 수가 많거나, 그래프가 희소할 때 효과적입니다.

동작 원리

간선 정렬 : 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬합니다.
초기화 : 각 정점을 별도의 집합으로 초기화합니다. 이를 위해 유니온-파인(Union-Find) 자료구조를 사용합니다.
간선 선택 : 정렬된 간선 목록에서 가장 작은 가중치의 간선부터 시작하여 다음을 수행합니다.
1. 이 간선이 두 개의 다른 집합을 연결하는 경우(즉, 사이클을 생성하지 않는 경우) 이 간선을 MST에 추가합니다.
2. 유니온-파인 자료구조를 사용하여 두 집합을 합칩니다.
반복 : 모든 간선이 처리될 때(n-1개의 간선이 선택될 때)까지 3단계를 반복합니다.

h-g 1 (1)
g-f 2 (2)
i-c 2 (3)
a-b 4 (4)
c-f 4 (5)
i-g 6 ➡️ 사이클이 생기므로 다음 간선 선택 (h-g-f-c-i 노드가 연결되어 있음)
h-i 7 ➡️ 사이클이 생기므로 다음 간선 선택 (h-g-f-c-i 노드가 연결되어 있음)
c-d 7 (6)
b-c 8 (7)
a-h 8
d-e 9 (8) ➡️ (9-1)개의 간선이 생성되었으므로 끝
f-e 10
b-h 11
d-f 14

이때 b-c, a-h 중 어떤 것을 선택하여도 상관 없습니다.

슈도 코드

초기화
- parent 배열 초기화: 모든 정점을 각각의 집합으로 설정합니다. 이는 `-1`로 설정된 배열로 표현됩니다.
- 간선의 힙 구성: 그래프의 모든 간선을 가중치에 따라 정렬하여 힙 자료구조로 만듭니다.
- ecount 초기화: 지금까지 검사한 간선의 수를 0으로 시작합니다.
- tcount 초기화: MST에 포함된 간선의 수를 0으로 시작합니다.
- T 초기화: MST를 저장할 집합을 공집합으로 시작합니다.

반복
- 조건: `tcount`가 `n-1`보다 작고, `ecount`가 `m`보다 작을 때까지 반복합니다. 여기서 `n`은 정점의 수, `m`은 간선의 수입니다.
- 간선 선택: 힙에서 가장 작은 가중치를 가진 간선을 선택하고, `ecount`를 증가시킵니다.
- 힙에서 제거 및 복원: 선택한 간선을 힙에서 제거하고 힙을 복원합니다.
- 집합 찾기 (FIND): 선택한 간선의 두 정점 `u`, `v`에 대해 각각의 집합을 찾습니다 (`r1`, `r2`).
- 집합 병합 (UNION): 두 정점이 다른 집합에 속해 있다면, 해당 간선을 MST에 추가하고, 두 집합을 병합합니다. 이때 `tcount`를 증가시킵니다.

종료 조건
- 모든 반복이 끝난 후, 만약 `tcount`가 `n-1`보다 작다면, 그래프가 연결되지 않았음을 의미하며 "network disconnected"라는 메시지를 출력합니다.

백준 문제 https://www.acmicpc.net/problem/14621

# 찾기 : 원소가 속한 집합의 대표 원소(또는 루트)를 찾음
def find(parent, i):
    if parent[i] == i:  # i 자기 자신이 i를 바라본다 = 해당 집합의 대표자를 찾았다.
        return i
    parent[i] = find(parent, parent[i])  # 경로 압축
    return parent[i]  # i의 부모가 가리키고 있는 정점부터 다시 대표자를 탐색

# 합집합 : 두 개의 집합을 합쳐서 하나의 집합으로 만듦
def union(parent, rank, x, y):
    # x 와 y 의 대표자를 찾자.
    root_x = find(parent, x)
    root_y = find(parent, y)

    if root_x == root_y:  # 이미 같은 집합이면 끝
        return

    # rank를 비교하여 더 작은 트리를 큰 트리 밑에 병합
    if rank[root_x] < rank[root_y]:
        parent[root_x] = root_y
    elif rank[root_x] > rank[root_y]:
        parent[root_y] = root_x
    else:
        # rank가 같으면 한쪽을 다른 쪽 아래로 병합하고 rank를 증가시킴
        parent[root_y] = root_x
        rank[root_x] += 1

def kruskal(n, edges):
    edges.sort(key=lambda x: x[2])  # 가중치(거리) 기준으로 정렬
    parent = [i for i in range(n+1)]
    rank = [0] * (n+1)
    mst_weight = 0
    cnt = 0

    for u, v, weight in edges:
        if find(parent, u) != find(parent, v): # 싸이클이 없다면
            cnt += 1
            union(parent, rank, u, v)
            mst_weight += weight
            if cnt == n - 1:  # n-1개의 엣지를 가진 최소 신장 트리를 완성했을 때
                return mst_weight

    return -1

# 학교의 수, 학교를 연결하는 도로의 개수
N, M = map(int, input().split())
# 남초 대학교면 M, 여초 대학교면 W
gender = [""] + input().split()
# u학교와 v학교가 연결되어 있으며 이 거리는 d
edges = []
for _ in range(M):
    u, v, d = map(int, input().split())
    if gender[u] == gender[v]:
        continue
    edges.append((u, v, d))
    
print(kruskal(N, edges))

크루스칼 알고리즘에 대해서 설명을 더 해보자면

간선들을 가중치(거리) 기준으로 정렬합니다.
parent와, rank 배열을 초기화 합니다.
간선들을 하나씩 검사하여 싸이클이 없는 경우에만 집합을 합칩니다.
연결된 간선의 가중치를 더하고, 간선의 수가 n-1이 되면 최소 신장 트리를 완성한 것으로 간주하고 그렇지 않으면 -1을 반환하도록 하였습니다.

시간 복잡도 차이 정리

프림 알고리즘의 시간 복잡도 : O(E log V) - E는 간선의 수, V는 정점의 수
크루스칼 알고리즘의 시간 복잡도 : (O(E log E)) 또는 (O(E log V))
- 유니온-파인 연산: 각 연산이 거의 상수 시간에 이루어지므로 (O(E alpha(V))),
  - 여기서 (alpha)는 아커만 함수의 역함수로 매우 느리게 증가하는 함수입니다.

저작자표시 비영리 변경금지

'Python' 카테고리의 다른 글

Python Cheat Sheets (0)	2024.06.30

현재글MST 최소 신장 트리

문과생의 작은 집

내 이름은 물리. 문과생이지요.

우선순위스케줄링, 프림 알고리즘, 프로세스 계층, 페이지 교체 알고리즘, 스레싱, 프로세스 상태, 문맥교환, 컴퓨터공학, 크루스칼 알고리즘, 선점형과 비선점형 스케줄링, 프로세스우선순위, 프레임 할당, 멀티 프로세스, 멀티 스레드, 최소비용신장트리, 다단계피드백스케줄링, 십육진수, 스케줄링 큐, CPU스케줄링, 요구 페이징,

Today :
Yesterday :

문과생의 작은 집