[알고리즘 / Python] 최소신장트리 (크루스칼 알고리즘)

1. 신장 트리 (Spanning Tree)

• 신장 트리는 모든 노드끼리 연결되어 있는 (모든 노드 간에 경로가 존재하는) 연결 그래프가 주어졌을 때, 모든 노드가 연결되지만 사이클이 존재하지 않는 부분 그래프를 의미한다.
• 그래프의 최소 연결 부분 그래프라고 할 수 있다.
• 여기서 최소 연결이란, 간선의 수가 최소가 되는 부분 그래프를 의미한다.
• n개의 노드가 있을 때 간선의 수는 n-1이 된다.

2. 최소 신장 트리

• 최소 신장 트리는 연결 그래프가 주어졌을 때, 가능한 신장 트리 중 가중치 합이 가장 작은 트리이다.

2.1. 최소 신장 트리의 특징

1. 간선의 가중치 합이 최소여야 한다.
2. 노드가 n 개일 때, 간선은 반드시 n-1 개다. (신장 트리 특징)
3. 사이클이 존재하지 않는다. (신장 트리 특징)

3. 크루스칼 (Kruskal) 알고리즘

• 시간복잡도: 간선의 개수가 m 일때, O(mlogm)
• 탐욕(그리디) 알고리즘을 이용하여 모든 노드들을 최소 간선 비용으로 연결하는 최적해를 구한다.

1. 간선들을 가중치를 기준으로 오름차순으로 정렬한다.
2. 정렬된 간선 리스트에서 가중치가 낮은 순서대로 간선의 사이클 발생 여부를 확인한다.
3. 사이클이 발생하지 않는다면, 해당 간선을 현재의 최소 신장 트리(MST)에 추가한다.

• 사이클 발생 여부는 부모노드가 같은지 여부를 통해 분별한다.
  • 분리집합 (서로소 집합) 알고리즘을 활용한다. (Union-Find 함수)
  • union 함수를 통해서 합쳐질 때, 서로의 부모가 이미 같다면 사이클 발생한 것이다.

3.1. Union-Find 함수

def find(x):
    # 자신이 루트이면 자기 자신 반환
    if x == parent[x]: 
        return x
    
    # 자신이 루트가 아니면 부모를 루트로 만듦
    else:
        parent[x] = find(parent[x])
    return parent[x]

def union(x,y):
    # 부모 노드 탐색
    x = find(x)
    y = find(y)
    
    # 부모를 합쳐 줌 
    if y < x:
        parent[x] = y
    else:
        parent[y] = x

3.2. Kruskal 함수

# 노드 수, 간선 수
n, m = map(int, input().split())

# ith 노드에 대한 부모 노드 초기화
parent = list(range(n+1))

# 간선 정보를 담을 리스트

edges = []
# 최소 신장 트리 가중치 합을 담을 변수
mst_cost = 0

# 간선 정보
for _ in range(m):
    x, y, cost = map(int, input().split())
    edges.append((cost,x,y))

# 간선 가중치에 대해 정렬
edges.sort(key = lambda a: a[0])

# 가중치가 작은 간선부터 크루스칼 알고리즘 수행
for i in range(e):
    cost, x, y = edges[i]

    # find 함수를 통해 부모가 같은지 여부 확인 -> 사이클 여부 체크 (아직 연결 안 됨)
    # 서로 부모가 다른 경우 최소 신장 트리(MST)에 추가
    if find(x) != find(y):
        mst_cost += cost
        # 확인한 뒤 union 함수를 통해 부모를 통일 시킴으로써 최소 신장 트리에 포함 시킴
        union(x,y)

print(mst_cost)