[자료구조/알고리즘] 신장 트리, 최소 신장 트리, 크루스칼 알고리즘 파이썬 구현

자료 출처: https://youtu.be/aOhhNFTIeFI

1. 신장 트리

그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

2. 최소 신장 트리

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

3. 크루스칼 알고리즘

대표적인 최소 신장 트리 알고리즘으로, 그리디 알고리즘으로 분류된다.

• 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
• 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
  • 사이클이 발생한 경우: 최소 신장 트리에 포함시키지 않음
  • 사이클이 발생하지 않은 경우: 최소 신장 트리에 포함시킴
• 위의 과정을 모든 간선에 대하여 반복한다.
• 최소 신장 트리에 포함된 간선의 비용을 모두 더한 값이 최종 비용이다.

4. 파이썬 구현

# 특정 원소가 속한 집합 찾기
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
    
    # a와 b가 같은 집합에 포함되어있지 않다면, 즉 사이클이 발생하지 않았다면
    if find_parent(parent, a) != find_parent(parent_b):
        # 사이클이 발생하지 않은 경우에만 집합에 포함시켜준다
        union_parent(parent, a, b)
        result += cost
        
print(result)

시간 복잡도는 O(ElogE)이다.