Algorithm Guidecomplexity: O(E log E)

크루스칼 (Kruskal MST)

모든 간선을 가중치 오름차순으로 정렬한 뒤, 사이클을 만들지 않는 간선만 차례로 채택해 최소 신장 트리(MST)를 만듭니다. 사이클 판별은 유니온-파인드(Union-Find)로 O(α)에 처리합니다.

01크루스칼 (Kruskal MST)

알고리즘 작동 원리 탐색

Kruskal 시작. 모든 간선을 가중치 오름차순으로 정렬하고, 각 노드를 자기 자신만의 집합으로 둡니다.

가장 가벼운 간선 AB(1)부터 봅니다. A와 B는 서로 다른 집합이라 이어도 사이클이 없어, MST에 넣고 두 집합을 합칩니다.

BC(2) · 서로 다른 집합이라 추가합니다. {A,B}와 C가 하나로 합쳐집니다.

AC(3) · A와 C는 이미 같은 집합입니다. 여기를 이으면 사이클이 생기므로 버립니다.

CD(4) · 다른 집합이라 추가합니다. D가 {A,B,C}에 합류합니다.

BD(5) · B와 D도 이미 한 집합입니다. 역시 사이클이 되므로 버립니다.

DE(6) · 마지막 집합 E가 합류합니다. 간선 4개(노드 5개−1)가 모여 MST가 완성됩니다.

완료 · MST = AB + BC + CD + DE, 총 가중치 13. CE(7)는 모두 한 집합이라 검사 없이 끝납니다.

Live Python

1def kruskal(n, edges):

2 parent = list(range(n))

3 def find(x):

4 while parent[x] != x:

5 x = parent[x]

6 return x

7 mst, total = [], 0

# sorted: 1,2,3,4,5,6,7

8 for w, u, v in sorted(edges):

9 if find(u) != find(v):

10 parent[find(u)] = find(v)

11 mst.append((u, v))

12 total += w

13 return mst, total

1 / 8

02 쉽게 이해하기

For Everyone

🔑핵심 동작

간선을 가중치가 작은 것부터 훑으며 사이클을 만들지 않는 것만 고릅니다. 어느 정점에서 시작하든 결과는 같습니다.

💡쉽게 말하면

간선을 가중치 순으로 정렬해 사이클을 만들지 않는 것만 채택합니다.

유니온-파인드로 사이클을 빠르게 판별해요.

📍어디에 쓰나

–최소 비용 네트워크 설계
–도로·통신망 구축

03 파이썬 구현 코드

크루스칼 (Kruskal MST)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def kruskal(n, edges):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x
    mst, total = [], 0
    for w, u, v in sorted(edges):
        if find(u) != find(v):
            parent[find(u)] = find(v)
            mst.append((u, v))
            total += w
    return mst, total