신장 트리

하나의 그래프가 있을 때 모든 노드를 포함하며 사이클이 존재하지 않는 부분 그래프

– 트리의 성립 조건 중 하나

크루스칼 알고리즘

최소한의 비용으로 신장 트리를 찾아야 할 경우 사용하는 알고리즘

• 최소 신장 트리 알고리즘 중 하나
• 가장 적은 비용으로 모든 노드를 연결하는 알고리즘

과정

1. 간선 데이터를 비용에 따라 오름차순 정렬
2. 간선을 하나씩 확인하며 현재 간선이 사이클을 발생시키는지 확인
   • 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
   • 사이클이 발생하는 경우 최소 신장 트리에서 제외
3. 모든 간선에 대해 과정 반복

핵심 원리

• 가장 거리가 짧은 간선부터 차례대로 집합에 추가
• 집합에 추가할 때 사이클을 발생시키는 간선은 제외하고 연결

예시

초기 테이블

1. 가장 짧은 간선 선택

• (3, 4) 선택
• 3, 4은 같은 집합이 아니므로 union 수행
• 집합: {3, 4}

2. 그 다음으로 비용이 적은 간선 선택

• (4, 7) 선택
• 4, 7은 같은 집합이 아니므로 union 수행
• 집합: {3, 4, 7}

3. 그 다음으로 비용이 적은 간선 선택

• (4, 6) 선택
• 4, 6은 같은 집합이 아니므로 union 수행
• 집합: {3, 4, 6, 7}

4. 그 다음으로 비용이 적은 간선 선택

• (6, 7) 선택
• 집합: {3, 4, 6, 7}
• 6, 7은 이미 같은 집합 내에 존재하므로 union 수행 X

5. 그 다음으로 비용이 적은 간선 선택

• (1, 2) 선택
• 1, 2는 같은 집합이 아니므로 union 수행
• 집합: {3, 4, 6, 7}, {1, 2}

6. 그 다음으로 비용이 적은 간선 선택

• (2, 6) 선택
• 2, 6은 같은 집합이 아니므로 union 수행
• 집합: {1, 2, 3, 4, 6, 7}

7. 그 다음으로 비용이 적은 간선 선택

• (2, 3) 선택
• 집합: {1, 2, 3, 4, 6, 7}
• 2, 3은 이미 같은 집합 내에 존재하므로 union 수행 X

8. 그 다음으로 비용이 적은 간선 선택

• (5, 6) 선택
• 5, 6은 같은 집합이 아니므로 union 수행
• 집합: {1, 2, 3, 4, 5, 6, 7}

9. 그 다음으로 비용이 적은 간선 선택

• (1, 5) 선택
• 집합: {1, 2, 3, 4, 6, 7}
• 1, 5는 이미 같은 집합 내에 존재하므로 union 수행 X

• 최종 비용 = 7 + 13+ 23+ 29 + 34 + 53 = 159

소스 코드

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


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)