최소비용 신장트리(Minimum Cost Spanning Tree)

학습 목표

- 신장트리(Spanning Tree) 개념과 특징을 이해할 수 있다

- 최소비용 신장트리(Minimum Cost Spanning Tree) 개념과 특징을 이해할 수 있다

- 최소비용 신장트리 사용 사례

- 구현 방법

 

신장 트리 개념과 특징

무향방 연결 그래프 $G=(V,E)$ 가 주어질때 모든 노드를 포함하고 연결되어 있으면서, 간선 비용의 합이 최소인 트리

- 하나의 그래프에서 많은 신장 트리가 존재할 수 있다

- 모든 정점이 연결되어 있어야 하고, 사이클이 존재해선 안된다.

- n개의 정점을 n-1개 간선으로 연결한다.

 

최소비용 신장트리 개념과 특징

신장 트리 중에서 가중치 합이 최소인 트리

 

최소비용 신장트리 사용 사례

1. 군집 분석(Cluster Analysis)

2. 필기 인식(Handwriting Recognition)

3. 이미지 분할(Image Segmentation)

4. 네트워크 구축(도로 건선, 회로 구성, 배관)

 

최소비용 신장트리 구현 방법

1. Kruskal Algorithm

개념 : Greedy Method 을 이용하여 가중 그래프의 모든 정점을 최소 비용으로 연결

동작 방식 

• 그래프 간선들을 가중치의 오름차순으로 정렬한다
• 정렬된 간선 리스트 중에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
  • 가장 낮은 가중치를 먼저 선택한다
  • 사이클을 형성하는 간선을 제외한다
• 해당 간선을 현재 MST의 집합에 추가한다

시간 복잡도

• 간선 e개를 정렬하는 시간에 좌우된다.

 

2. Prim Algorithm

개념 : Greedy Method 을 이용하여 가중 그래프의 모든 정점을 최소 비용으로 연결
동작 방식 :

• 임의의 시작 정점을 선택. 집합에 삽입
• 또한, 시작 정점의 인접한 간선을 리스트에 삽입
• 가장 가중치가 낮은 간선의 정점을 연결(해당 간선의 인접 정점은 집합에 포함되지 않은 것이어야 한다).
• 해당 간선은 리스트에서 제거

 

시간 복잡도

• $O(n^2)$
• 적은 숫자의 간선을 가지는 희소 그래프(Sparse Graph)의 경우 Kruskal 알고리즘이 적합하고,
• 간선이 많은 밀집 그래프(Dense Graph)의 경우 Prim 알고리즘이 적합하다

 

대표 문제

[최소 스패닝 트리, boj1197] [풀이]

[도시 분할 계획, boj1647] [풀이]

[팀결성, 커리큘럼] [풀이] 

 

[Reference]

[1] en.wikipedia.org/wiki/Minimum_spanning_tree

[2] gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

 

---

알고리즘 시각화와 코드 

1. Kruskal Algorithm

 

 

2. Prim Algorithm

# Kruskal Algorithm

parent = {}
rank = {}

def find(node):
    # path compression 기법, ★node의 부모가 최 상위 노드가 된다. 이때 트리의 모양이 바뀐다!!
    if parent[node] != node:
        parent[node] = find(parent[node])
    return parent[node]
    
def union(node_v, node_u):
    root1 = find(node_v)
    root2 = find(node_u)
    
    # union-by-rank 기법
    if rank[root1] > rank[root2]:
        parent[root2] = root1
    else:
        parent[root1] = root2
        if rank[root1] == rank[root2]:
            rank[root2] += 1


def make_set(node):		
    parent[node] = node # 자신의 부모 노드는 자기 자신으로 초기화 한다.
    rank[node] = 0

def kruskal(graph): # 정렬 시간이 대부분의 시간을 결정, O(ElogE)
    mst = []
    
    # 1. 초기화, O(v)
    for node in graph['vertices']:
        make_set(node)
    
    # 2. 간선 가중치 기반 정렬, O(ElogE)
    edges = graph['edges']
    edges.sort()
    
    # 3. 간선 연결, O(1)(왜냐하면, union-by-rank과 path compression 기법 때문에)
    for edge in edges:
        weight, node_v, node_u = edge
        if find(node_v) != find(node_u): # 공통 조상이 같지 않다면, 
            union(node_v, node_u)        # ★트리 모양을 바꾸면서 동시에 루트 노드를 비교한다.
            mst.append(edge)             # 트리 모양을 바꿔 놓으면, 다음번 비교시에 시간이 줄어든다
                                         # (path compression 핵심)
    return mst    

'''
graph = {
    'vertices': ['A', 'B', 'C', 'D', 'E', 'F', 'G'],
    'edges': [
        (7, 'A', 'B'),
        (5, 'A', 'D'),
        (7, 'B', 'A'),
        (8, 'B', 'C'),
        (9, 'B', 'D'),
        (7, 'B', 'E'),
        (8, 'C', 'B'),
        (5, 'C', 'E'),
        (5, 'D', 'A'),
        (9, 'D', 'B'),
        (7, 'D', 'E'),
        (6, 'D', 'F'),
        (7, 'E', 'B'),
        (5, 'E', 'C'),
        (7, 'E', 'D'),
        (8, 'E', 'F'),
        (9, 'E', 'G'),
        (6, 'F', 'D'),
        (8, 'F', 'E'),
        (11, 'F', 'G'),
        (9, 'G', 'E'),
        (11, 'G', 'F')
    ]
}
'''

 

# Prim Algorithm

from collections import defaultdict
from heapq import *

def prim(start_node, edges): # O(ElogE) 
	mst = []
    adjacent_edges = defaultdict(list)
    for weight, n1, n2 in edges: # 모든 간선 정보를 저장
    	adjacent_edges[n1].append((weight, n1, n2)) # n1 key에 연결된 간선 정보 삽입
        adjacent_edges[n2].append((weight, n1, n2)) # n2 key에 연결된 간선 정보 삽입
        
    connected_nodes = set(start_node)
    candidate_edge_list = adjacent_edges[start_node] # 시작 정점의 인접 간선 정보를 리스트에 삽입
    heapify(candidate_edge_list)                     # 가장 가중치가 낮은 노드를 찾기 위해 최소힙정렬

	while candidate_edge_list:
    	weight, n1, n2 = heappop(candidate_edge_list) #선택한 간선은 제거
        if n2 not in connected_nodes;                 # 인접 정점에 '연결 노드 집압'에 없다면
        	connected_nodes.add(n2)               # 집합에 n2 노드 추가
            mst.append((weight, n1, n2))
            
            for edge in adjacent_edges[n2]:                 # n2 노드 간선 중에
            	if edge[2] not in connected_nodes:          # '연결 노드 집합'에 없는 정점들만
                	heappush(candidate_edge_list, edge) # '간선 리스트'에 삽입
	return mst

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

 

---

▶ Union-Find 알고리즘 과정