[알고리즘] 크루스칼 알고리즘이란? (최소 신장 트리 찾기)

1️⃣ 신장 트리란?

크루스칼 알고리즘은 '최소 신장 트리 알고리즘'이다. 즉, 최소 신장 트리를 찾기 위한 알고리즘이라는 것이다.

최소 신장 트리란 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 의미한다.

 

크루스칼 알고리즘을 설명하기 전에 신장 트리에 대해 설명을 하고 넘어가겠다.

 

신장트리란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.

신장트리 설명 이미지

모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건에 해당한다. 따라서 이런 그래프를 신장 트리라고 부르는 것이다.

 

신장 트리는 동일한 그래프에서도 여러 개의 신장트리를 찾을 수 있다.

 

하지만 가능한 한 최소한의 비용으로 신장 트리를 찾아야 하는 상황이 존재한다.

따라서 신장 트리 중에서 최소 비용으로 만들 수 있는 신장트리를 찾는 알고리즘이 필요하며, 이때 사용하는 알고리즘이 '최소 신장 트리 알고리즘'이다. 대표적인 최소 신장 트리 알고리즘이 크루스칼 알고리즘이다.

 

아래 그림에서 최소 신장 트리를 찾아보면, (d)가 모든 거리의 합이 6으로 가장 작으므로 최소 신장트리가 된다.

 

2️⃣ 크루스칼 알고리즘이란?

위에 설명한 것과 같이 크루스칼 알고리즘은 최소 비용으로 만들 수 있는 신장트리를 찾기 위한 알고리즘이며, 그리디 알고리즘에 분류된다.

 

먼저 모든 간선에 대해 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시키면 된다. 이때 사이클을 발생시킬 수 있는 간선의 경우, 집합에 포함시키지 않아야 한다.

 

구체적인 알고리즘은 다음과 같다.

1. 간선 데이터를 비용에 따라 오름차순 정렬한다.
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
   • 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
   • 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
3. 모든 간선에 대해 2번의 과정을 반복한다.

 

만약 사이클이 발생하는지를 확인하는 방법을 모른다면 하단의 글을 참고하도록 하자.

[알고리즘] Union-Find(유니온 파인드)로 무방향 그래프에서 사이클(cycle) 찾기

 

📂 기본 예제 코드(Python)

아래 코드는 크루스칼 알고리즘을 구현한 코드이다.

[입력]
7 9
1 2 29
1 5 75
2 3 35
2 6 34
3 4 7
4 6 23
4 7 13
5 6 63
6 7 25

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, x, y):
    x = find(parent, x)
    y = find(parent, y)

    if x < y:
        parent[y] = x
    else:
        parent[x] = y

v, e = map(int, input().split())

graph = []
parent = [i for i in range(v+1)]
for _ in range(e):
    a, b, cost = map(int, input().split())
    graph.append((cost, a, b))

graph.sort()
answer = 0 # 최소 신장 트리 비용의 합
for cost, a, b in graph:

    if find(parent, a) != find(parent, b):
        union(parent, a, b)
        answer += cost

print(answer)