[알고리즘] 크루스칼

프림과 크루스칼 알고리즘은 최소 신장 트리를 구하는 대표적인 알고리즘이다. 먼저 최소 신장 트리가 무엇인지 알아본 후에 유니온 파인드를 적용시킨 크루스칼 알고리즘을 알아본다.

---

최소 신장 트리

N개의 노드로 이루어진 그래프가 있다. 이 그래프에는 다양한 부분 그래프가 존재할 수 있다. 이때 부분 그래프를 신장 트리라하며 N개의 노드글 N-1개의 간선으로 연결하고 순환되지 않는 구조를 가져야만 신장 트리라 할 수 있다. 이러한 신장 트리 중에서 연결하는데 가장 적은 비용이 드는 신장 트리를 최소 신장 트리라 한다.

 

개념

크루스칼 알고리즘은 유니온 파인드와 그리디 알고리즘의 개념을 활용하였다. 먼저 신장 트리가 되기 위해서는 N-1개의 간선으로 N개의 노드를 연결해야 하며 순환되지 않는 구조를 가져야 한다. 이를 위해 유니온 파인드를 통해 신장 트리를 구할 수 있다. 노드들이 속한 집합이 한 곳을 가리킨다면 신장 트리라 볼 수 있을 것이기 때문이다.

 

또한 최소 신장 트리를 위해서 그리디 알고리즘을 활용한다. 두 개의 노드를 연결하기 위해 드는 비용을 기준으로 오름차순 정렬하여 간선을 하나씩 선택한다. 이는 간선을 선택할 때마다 최소 비용을 선택하는 것과 같다.

 

위의 두 개의 알고리즘을 합쳐서 크루스칼 알고리즘을 구현할 수 있다. N개의 섬이 있다고 가정한다. N개의 섬을 순환되지 않는 구조로 다리를 연결하는데 드는 최소 비용을 구해보자. M개의 간선 정보가 주어지고 여기서 N-1개의 간선을 선택하여 최소 신장 트리를 구해야 한다.

 

구현

• N을 입력받는다.
• 초기에 각각의 섬들이 자기 자신을 가리키도록 설정한다.

# 자기 자신을 가리키도록 초기화 : make_set
N = 5
p = [n for n in range(N)]

• 유니온 파인드를 통해 두 개의 섬이 연결되었는지 판단한다.

# a 노드의 대표노드를 찾아주기
def find_set(a):
    # 자기 자신을 가리키면 a를 그대로 반환
    if p[a] == a:
        return a
    else:
        # 다른 노드가 대표노드라면 a가 속한 최상위 노드 찾기
        b = find_set(p[a])
        p[a] = b
        return b

# b노드의 대표 노드를 a로 설정하기
def union(a, b):
    a = find_set(a)
    b = find_set(b)
    if a != b:
        p[b] = a

• 간선의 정보인 graph는 비용을 기준으로 오름차순 정렬되었다.
• 두 개의 섬의 루트 집합이 다를 때는 아직 연결된 것이 아니다.
• 따라서 두 개의 섬을 union 연산을 통해 연결하고 다리를 놓는데 드는 비용을 c만큼 더한다.
• 이때 연결한 다리인 bridge가 N-1일 때 종료한다.

# a->b로 갈 때 c 비용
for a, b, c in graph:
    # 대표 노드가 다르다면 a에서 b로 건널 수 있다.
    if find_set(a) != find_set(b):
        # 이제 a에서 b로 건넜기 때문에 b의 대표노드를 a로 설정한다.
        union(a, b)
        # 지금까지 건너온 다리를 증가시키고
        bridge += 1
        # 비용을 C만큼 증가시킨다.
        total += c
     # N-1만큼의 다리를 건너왔다면 모든 섬을 방문한 것이기 때문에 종료한다.   
     if bridge == N-1:
        break
        
# 최종적으로 모든 섬을 한 번씩 방문할 때 최소 통행료는 total이 된다.