Algorithm Guidecomplexity: O(E log E)

크루스칼 (Kruskal MST)

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

01 Explore How It Works

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 Understand It Simply

For Everyone

🔑Analogy

가장 싼 도로부터 깔되, 이미 연결된 마을은 건너뛰는 것.

💡In Plain Words

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

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

📍Where It's Used

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

03 Python Implementation

A clean, readable reference implementation of the core logic of 크루스칼 (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