Algorithm Guidecomplexity: O(E log E)

크루스칼 (Kruskal MST)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

HOVER OR SCROLL

Kruskal MST

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

Logic Node1 / 8

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

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