최소 스패닝 트리

스패닝 트리

스패닝 트리 또는 신장 트리(Spanning Tree)는 모든 노드를 포함하며 사이클이 존재하지 않는 부분 그래프를 의미한다. 즉, 모든 노드가 서로 연결되어 있되, 하나의 노드에서 나온 간선이 자기 자신으로 돌아오지 않아야 신장 트리의 조건을 만족한다.

최소 스패닝 트리

간선의 가중치 또는 비용이 주어질 때, 신장 트리를 이루는 모든 간선 비용의 합이 최소가 되는 트리를 ‘최소 스패닝 트리(Minimum Spanning Tree)’라고 한다.

크루스칼 알고리즘

크루스칼 알고리즘은 가장 적은 간선 비용으로 모든 노드를 연결할 수 있는 최소 신장 트리를 찾는 알고리즘이다. 먼저 모든 간선을 비용에 따라 정렬한 후, 가장 짧은 간선부터 차례대로 선택한다. 이때, 매 단계에서 사이클이 발생하는지 판별하고, 사이클이 발생하는 경우 해당 간선을 제외한다. 이렇게 반복하여 최소 신장 트리를 완성한다.

간선 정보를 담은 리스트를 오름차순 정렬
최소 비용 간선을 하나씩 확인하며 사이클 발생 여부를 판별한다.
1. 사이클이 아닌 경우, 최소 신장 트리에 포함
2. 사이클이 발생하는 경우, 포함하지 않음
모든 간선에 대해 2번 과정을 반복한다.

크루스칼 알고리즘은 사이클의 여부를 판별하기 위해 union-find 를 사용하기 때문에, 서로소 집합 알고리즘의 연장으로 볼 수 있다.

크루스칼 알고리즘 예시 코드

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
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)

최소 스패닝 트리

SERIES: 알고리즘 (9)

스패닝 트리