[알고리즘] 크루스컬(kruskal) 알고리즘

크루스컬 알고리즘(Kruskal Algorithm)

 가중치가 있는 무방향 그래프를 최소 신장 트리로 만드는 알고리즘입니다.

 최소 신장 트리는 가중치가 최소인 순환이 없는 무방향 그래프 입니다.

 순환이 없으므로 간선 수는 정점 수 - 1이 됩니다.

 크루스컬 알고리즘은 Greedy Algorithm에 속하며, 매 번 순환이 되지 않도록 가중치가 가장 적은 다음 간선을 선택합니다. 

 시잔복잡도 O(ElogN)

 

작동 원리

(1) 간선을 가중치를 기준으로 정렬합니다.

(2) 가장 가중치가 작은 간선(u, v)을 선택합니다.

(3) union find 알고리즘을 통해 u와 v를 병합합니다.

(4) union find 알고리즘은 각 정점을 분리 집합으로 만들고 서로 다른 집합에 속해있는 정점을 하나의 집합으로 병합합니다.

(4) 간선을 추가하여 순환이 만들어지는 경우에 union find 알고리즘에 의하여 간선이 연결되지 않습니다.

(5) 최종적으로 연결된 그래프가 MST가 됩니다.

 

파이썬 코드

# 크루스컬 알고리즘
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N = int(input()) # 정점 수 입력 받기
M = int(input()) # 간선 수 입력 받기
parent = [0] * (N+1) # 루트 노드를 저장할 자료구조
rank = [0] * (N+1) # 정점의 rank를 저장할 자료구조
edges = [[] for i in range(M+1)] # 간선 정보를 저장할 자료구조

# parent 초기화, 자기 자신을 루트 노드로 설정
for i in range(1, N+1):
    parent[i]=i

# 간선 정보 입력 받기
for i in range(1, M+1): # 간선 수 만큼 반복
    a, b, c = map(int,input().split()) # 간선 정보 입력 (출발 정점, 도착 정점, 비용)
    edges[i].extend([c, a, b]) # 비용, 출발 정점, 도착 정점

# union find algorithm
def find(a): # a 정점의 루트 노드 탐색
    if parent[a] == a: # a가 루트 노드이면, a 반환
        return a
    p = find(parent[a]) # 루트 노드 탐색
    parent[a] = p # a의 루트 노드 갱신
    return parent[a]

def union(a, b): # a와 b 집합을 병합
    a = find(a) # a의 루트 노드 탐색
    b = find(b) # b의 루트 노드 탐색
    if a == b: # 루트 노드가 동일하면, 동일한 집합
        return
    if rank[a] > rank[b]: # rank가 낮은 집합을 rank가 높은 집합으로 병합
        parent[b] = a # 병합
    else:
        parent[a] = b # 집합 병합
        if rank[a] == rank[b]: # 두 랭크가 동일하면
            rank[b] += 1 # 랭크 +1

# 크루스컬 알고리즘
def kruskal(edges):
    edges.sort() # 비용을 기준으로 정렬
    total = 0 # 최종 비용
    MST = [] # 최소 신장 트리
    # 간선 연결
    for edge in edges:
        if not edge: # 0 번째 edge 생략
            continue
        cost, a, b = edge # 간선 정보 추출
        if find(a) != find(b): # 서로 다른 집합인 경우
            union(a,b) # a, b 병합
            total += cost # 비용 갱신
            MST.append((a,b)) # 최소 신장 트리

    return total, MST

total, MST = kruskal(edges)

 

관련 문제

1922번: 네트워크 연결

 

출처

[Python] Kruskal Algorithm (크루스칼 알고리즘)