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

최소신장트리란 신장트리 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 지칭한다.

여기서 신장 트리란 모든 정점이 연결된 그래프다.

 

조건

1. 연결 그래프의 부분 그래프이며 그래프에서 모든 정점을 표현한다.

2. 정점간 서로 연결 되어있어야 한다(N개의 정점이라면 N-1개의 간선)

3. 사이클이 존재하면 안된다.

4. 연결 그래프에서 나올 수 있는 신장트리는 1개가 아닌 다수이다.

-> 최소신장트리는 그래프에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것이다.

 

MST의 특징

1. 간선의 가중치의 합이 최소여야한다.

2. N개의 정점을 가지는 그래프에 대해 반드시 (N-1)개의 간선만을 사용한다.

3. 사이클이 포함되어선 안된다.

 

MST 구현방법

먼저 프림(Prim)에 대해 다뤄보겠다.

1.1. 변수 초기화 : 그래프의 정점 수, MST에 포함된 간선들을 저장할 리스트, MST의 총 가중치, 각 정점이 MST에 포함되었는지, 여부를 추적하는 리스트, 우선순위 큐를 초기화한다.

 

1.2. 우선순위 큐에서 가중치 간선을 꺼낸다.

 

1.3. 방문 표시후 간선을 mst_edges에 추가한다.

 

1.4. 현재 정점에서 연결된 모든 간선을 우선순위 큐에 추가한다.

a- graph[v]의 인접 정점들과 가중치를 불러온다.

b- next_v 정점이 아직 방문되지 않았고 next_weight가 0보다 큰지 확인

c- 우선순위 큐에 추가

 

1.5. 반복: 우선순위 큐가 빌 때까지 해당 과정을 반복한다.

 

프림의 시/공간 복잡도

1. 인접 행렬 사용시: O(V**2)     /     O(V**2)

2. 인접 리스트 사용시 : O(logV)    /     O(V+E)

 

아래는 프림 알고리즘 전체 코드 구현 예제이다.

import heapq

def prim_mst(graph):
    num_nodes = len(graph)  # 그래프의 정점 수
    mst_edges = [] # MST에 포함된 간선들을 저장하는 리스트
    total_weight = 0 # 총 가중치 설정
    visited = [False] * num_nodes # 정점이 MST에 포함되었는지 여부 (리스트)
    min_heap = [(0, 0, 0)] # 우선순위 큐 초기화 (weight, start, end)
    
    while min_heap: # 큐가 비어있지 않을 동안 계속
        weight, u, v = heapq.heappop(min_heap) # 큐에서 최소 가중치를 꺼냄
        # 이미 방문한 정점이면 무시
        if visited[v]: 
            continue
        visited[v] = True # 방문 않나 정점이나 방문 표시
        if u != v: # 시작 정점이 아닌 경우에만
            mst_edges.append((u, v, weight)) # 간선을 MST에 추가
            total_weight += weight # 총 가중치에 간선의 가중치 더하기
        for next_v, next_weight in graph[v]: # 연결된 정점과 가중치 불러오기
            if not visited[next_v]: # 만약 방문하지 않았다면
                heapq.heappush(min_heap, (next_weight, v, next_v)) # 큐에 추가
    return mst_edges, total_weight # 종료(MST의 간선들과 총 가중치 반환)
    
graph = [     # 예제 그래프(인접 리스트)
    [(1, 2),(3, 6)],
    [(0, 2), (2, 3), (3, 8), (4, 5)],
    [(1, 3), (4, 7)],
    [(0, 6), (1, 8), (4, 9)],
    [(1, 5), (2, 7), (3, 9)]
]
mst_edges, total_weight = prim_mst(graph)
print(mst_edges)   # [(0, 1, 2), (1, 2, 3), (1, 4, 5), (0, 3, 6)]
print(total_weight) # 16

 

다음은 크루스칼(Kruskal)알고리즘으로 풀어보자

2.1. 변수 초기화 : 정점의 수 V, 간선의 수가 e일 때, 각 정점의 부모를 자기 자신으로 초기화한다.

 

2.2: 간선 정보 입력 및 정렬: 각 간선의 정보를 입력받아(비용, 정점1, 정점2)형태로 리스트에 저장한 후, 비용을 기준으로 오름차순 정렬한다.

 

2.3. 크루스칼 알고리즘 수행

a. find 연산: 특정 원소의 부모를 재귀적으로 찾아 반환

b. union 연산: 두 원소가 속한 집합을 합친다.

c. kruskal 알고리즘 수행

import sys
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화
for i in range(1, v + 1): # 각 정점의 부모를 자신으로 설정
    parent[i] = i
    
def find_parent(parent, x): # 부모 테이블에서 X를 찾고
    if parent[x] != x: # X가 자기 자신이 아니라면
        parent[x] = find_parent(parent, parent[x]) # 해당 X로 다시 재귀호출
    return parent[x] 

# union 연산 : 두 원소가 속한 집합을 합침
def union_parent(parent, a, b):
    a = find_parent(parent, a) # a의 부모 찾기
    b = find_parent(parent, b) # b의 부모 찾기
    if a < b:
        parent[b] = a # b의 부모를 a로 한다
    else:
        parent[a] = b # a의 부모를 b로 한다
        
edges = []  # 간선 정보를 담을 리스트
total_cost = 0 # 총 비용 설정

for _ in range(e):  # 간선 정보 입력 받기
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))
    
    edges.sort() # 간선 오름차순 정렬
    
for edge in edges: # 간선 정보 하나씩 확인하며 크루스칼 알고리즘 수행
    cost, a, b = edge 
    # find 연산 후 부모노드가 다르면(사이클이 없다는 뜻)
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        total_cost += cost # 총 비용 갱신
print(total_cost) # 총 비용 출력

 

-크루스칼 알고리즘의 시/공간 복잡도:

Union-find 자료구조를 사용하면 시간복잡도 : (O(ElogE)), 공간 복잡도(O(V+E)

 

 

 

 

요약하자면

1. 프림 알고리즘 : 정점 중심의 최소신장트리 알고리즘이고 한 정점에서 시작하여 인접한 간선 중 최소 비용의 간성을 선택하며 확장

2. 크루스칼 알고리즘 : 간선 중심의 최소신장트리 알고리즘이며 모든 간선을 비용 기준으로 정렬한 후, 최소 비용의 간선부터 선택하여 구성.