[알고리즘 개념] 최소 신장 트리(MST)

0. 최소 신장 트리(MST)

• 최소한의 비용으로 구성되는 신장 트리

신장트리란?

• 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
  -> 트리의 조건이기도 함

대표적인 알고리즘 2가지

• 크루스칼 알고리즘
• 프림 알고리즘

1. 크루스칼 알고리즘

신장 트리에 하나하나 간선을 더해가며 만드는 방법

1. 간선 데이터를 비용에 따라 오름차순으로 정렬
2. 간선을 하나씩 확인하여 현재의 간선이 사이클을 발생시키는지 확인
   2-1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
   2-2. 사이클이 발생하는 경우 최소 신장트리에 포함 X

* 시간 복잡도 : O(ElogE) , 이때 E는 간선의 개수

#특정 원소가 속한 집합을 찾기(find 연산)
def find_parent(parent,x):
    #루트 노드를 찾을 떄까지 재귀 호출
    if parent[x]!= x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]

#두 원소가 속한 집합을 합치기(union 연산)
def union_parent(parent,a,b):
    a=find_parent(parent, a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b

#노드의 개수와 간선(union 연산)의 개수 입력 받기
v,e = map(int, input().split())
parent = [0] * (v+1) #부모 테이블 초기화하기

#모든 간선을 담을 리스트와, 최종 비용을 담을 변수
edges=[]
result=0

#부모 테이블상에서, 부모를 자기자신으로 초기화
for i in range(1,v+1):
    parent[i]=i

#모든 간선에 대한 정보를 입력받기    
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
    #사이클이 발생하지 않는 경우에만 집합에 포함
    if find_parent(parent,a)!=find_parent(parent,b):
        union_parent(parent,a,b)
        result+=cost
        
print(result)

2. 프림 알고리즘

시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법
크루스칼과 다른 점은 신장 트리에 정점을 더해가는 방법이다.

1. 시작 단계에서는 시작 정점만 MST 집합에 포함
2. 앞에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장함, 낮은 가중치를 먼저 선택
3. 트리가 N-1개의 간선을 가질 때까지 반복

💻 코드
A. Collections 라이브러리의 defaultdict 이용

# key에 대한 값을 지정하지 않았을 때 빈리스트로 초기화함
from collections import defaultdict

list_dict = defaultdict(list)
print(list_dict['key1'])

list_dict2 = dict()
print(list_dict2['key1'])
edges = [
    (7, 'A', 'B'), (5, 'A', 'D'),
    (8, 'B', 'C'), (9, 'B', 'D'), (7, 'B', 'E'),
    (5, 'C', 'E'),
    (15, 'D', 'E'), (6, 'D', 'F'),
    (8, 'E', 'F'), (9, 'E', 'G'),
    (11, 'F', 'G')
]

from collections import defaultdict
from heapq import *

def prim(first_node, edges):
	mst = []
    # 해당 노드에 해당 간선을 추가
    adjacent_edges = defaultdict(list)
    for weight, node1, node2 in edges:
    	adjacent_edges[node1].append((weight, node1, node2))
        adjacent_edges[node2].append((weight, node2m node1))
    
    # 처음 선택한 노드를 연결된 노드 집합에 삽입
    connected = set(first_node)
    # 선택된 노드에 연결된 간선을 간선 리스트에 삽입
    candidated_edge = adjacent_edges[first_node]
    # 오름 차순으로 정렬
    heapify(candidated_edge)
    
    while candidated_edge:
    	weight, node1, node2 = heappop(candidated_edge)
        # 사이클 있는지 확인 후 연결
        if node2 not in connected:
        	connected.add(node2)
            mst.append((weight, node1, node2))
            
            for edge in adjacent_edges[node2]:
            	if edge[2] not in connected:
                	heappush(candidated_edge, edge)
     
     return mst

B. 우선순위 큐를 통한 프림 알고리즘

from heapdict import heapdict

def prim(graph, first):
	mst = []
    keys = heapdict()
    previous = dict()
    total_weight = 0
    
    # 초기화
    for node in graph.keys()"
    	keys[node] = float('inf')
        previous[node] = None
    
    keys[first], previous[first] = 0, first
    
    while keys:
    	current_node, current_key = keys.popitem()
        mst.append([previous[current_node], current_node, current_key])
        total_weight += current_key
        for adjacent, weight in graph[current_node].items():
        	if adjacent in keys and weight < keys[adjacent]:
            	keys[adjacent] = weight
                previous[adjacent] = current_node
    return mst, total_weight
    
graph = {
    'A': {'B': 7, 'D': 5},
    'B': {'A': 7, 'D': 9, 'C': 8, 'E': 7},
    'C': {'B': 8, 'E': 5},
    'D': {'A': 5, 'B': 9, 'E': 15, 'F': 6},
    'E': {'B': 7, 'C': 5, 'F': 8, 'G': 9},
    'F': {'D': 6, 'E': 8, 'G': 11},
    'G': {'E': 9, 'F': 11}
}

mst, total_weight = prim(graph, 'A')
print(mst)
print(total_weight)

크루스칼 vs 프림

• 프림의 시간 복잡도 : O(Elog V)
• 크루스칼의 시간 복잡도 : O(Elog E)

따라서 그래프 내의 간선이 많은 경우 -> 프림 알고리즘
간선이 적은 경우 -> 크루스칼 알고리즘 유리

v : 노드, E : 간선

차이점

• 크루스칼 : 유니온 파인드 사용/ 프림 : 우선순위 큐 사용
• 크루스칼 : 가중치가 작은 간선부터 차례로 그래프 형성
• 프림 : 특정 노드를 시작으로 다른 노드를 하나씩 연결해 확장

Ref) https://velog.io/@chosj1526/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%94%84%EB%A6%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Prims-Algorithm