[알고리즘] 크루스칼 알고리즘

1. 크루스칼 알고리즘

• 최소 신장 트리 알고리즘 = 가장 적은 간선 비용으로 모든 노드를 연결
• 그리디 알고리즘으로 분류

동작과정

1. 주어진 모든 간선 정보에 대한 간선 비용이 낮은 순서(오름차순)로 정렬
2. 정렬된 간선 정보를 하니씩 확인하면서 현재의 간선이 노드들 간의 사이클을 발생시키는지 확인

• 노드들 간의 사이클이 발생하는지 여부 = 노드들의 부모노드가 같다면 사이클이 발생, 같지 않다면 사이클이 발생하지 않음을 의미

3. 만약 사이클이 발생하지 않은 경우 최소 신장 트리에 포함시키고,
   사이클이 발생한 경우, 최소 신장 트리에 포함시키지 않음
4. 1번~3번 과정을 모든 간선 정보에 대해 반복 수행

예시로 보는 동작과정

• [초기 단계] 그래프의 모든 간선 정보에 대하여 오름차순 정렬을 수행한다
• [Step 1] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (3,4)를 선택하여 처리한다
• [Step 2] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (4,7)을 선택하여 처리한다
• [Step 3] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (4,6)을 선택하여 처리한다
• [Step 4] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (6,7)을 선택하여 처리한다
• [Step 5] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (1,2)를 선택하여 처리한다
• [Step 6] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (2,6)을 선택하여 처리한다
• [Step 7] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (2,3)을 선택하여 처리한다
• [Step 8] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (5,6)을 선택하여 처리한다
• [Step 9] 아직 처리하지 않은 간선 중에서 가장 짧은 간선인 (1,5)를 선택하여 처리한다
• [알고리즘 수행 결과] 최소 신장 트리에 포함되어 있는 간선의 비용만 모두 더하면, 그 값이 최종 비용에 해당한다
• 다른 예시

소스코드 (Python)

# 특정 원소가 속한 집합을 찾기
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)

참고
https://freedeveloper.tistory.com/389
https://techblog-history-younghunjo1.tistory.com/262