크루스칼 알고리즘 - Python

오늘은 크루스칼 알고리즘에 대해서 알아보겠습니다.

크루스칼 알고리즘은 기본적으로 그리디 알고리즘에 속하는데요.

여러개의 노드를 최소비용으로 연결하는 것을 목표로 하고 있습니다.

이번 글은 아래의 자료를 바탕으로 작성됐습니다.

• 안경잡이 개발자 (크루스칼 알고리즘)
• 위키백과 (크루스칼 알고리즘)
• Union-find 알고리즘 (sunghyunpatricklee)

 

이 글에서 알아볼 내용

• 크루스칼 알고리즘이란
• 핵심 아이디어
• 예제 문제
• 마치면서

 

크루스칼 알고리즘이란

"MST (Minimum Spanning Tree) 를 찾기위한 알고리즘". 크루스칼 알고리즘을 설명하는 핵심적인 문장입니다. 그렇다면 MST 는 도대체 무엇일까요? "그래프의 노드들을 가장 적은 연결, 비용으로 모두 연결한트리". 크루스칼 알고리즘은 이런 문제를 해결하는데 효과적인 알고리즘입니다. 

 

핵심 아이디어

그리디 알고리즘. 크루스칼 알고리즘이 속해있는 분류입니다. 매 순간 최선의 값을 선택하여 알고리즘을 전개하죠. 간단하게 생각해봅시다. 가장 작은 가중치 순서대로 연결하면 가장 적은 비용으로 연결할 수 있지 않을까요? 정말 그리디 알고리즘 다운 발상입니다. 하지만 이걸로는 부족합니다. Minimum 은 달성할 수 있지만. Spanning Tree 는 구현에 실패합니다. Spanning Tree 는 (Node 의 수 - 1) 의 간선을 가집니다. 다음은 Spanning Tree 를 설명하는 그림입니다.

 

 

왼쪽 그림은 사이클을 형성한 그래프의 그림입니다. 그 반면 오른쪽 그림은 (Node - 1) 의 간선 숫자를 가진 Spanning Tree 입니다. Spanning Tree 를 만드는 방법은 간단합니다. 그냥 싸이클을 안만들면 됩니다. 그렇다면 싸이클을 안만든다는 것을 어떻게 알 수 있을까요? 

 

Union-find 알고리즘. 이를 활용하면 효과적으로 싸이클을 체크할 수 있습니다. Union find 알고리즘은 효과적으로 그룹을 형성 하게 해줍니다. 자세한 건 제가 작성한 Union-find 알고리즘을 봐주세요. 같은 그룹에 속했다는 것은 이미 연결됐다는 것을 뜻합니다. 만약 그런데 한번 더 연결하게 되면 싸이클이 형성되겠죠. 따라서 같은 그룹에 속했다면 연결을 하지 않고. 속한게 아니라면 아직 연결이 안됐다는 뜻이니 연결하면 됩니다. 이를 통해 우리는 Spanning Tree를 구현할 수 있게 됩니다.

 

작은 가중치 순서대로 정점들을 연결하되. 싸이클을 확인하면서 연결하면. 크루스칼 알고리즘의 완성이자 MST 를 구현하는 방법이 됩니다.

 

예제 문제

예제 문제로는 백준 문제 10021 (Watering the fields) 를 간략화 해서 풀어보겠습니다.[[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6], [7, 7], [8, 8]] 모두를 최소비용으로 연결한 값은 얼마일까요? 각 노드 간의 거리는 유클리드 거리로 하겠습니다. 당연히 sqrt(98) 일 것 입니다. 하지만 이걸 크루스칼 알고리즘으로 MST 를 만들어 풀어보겠습니다. 

 

import heapq
from math import sqrt

def find(par, uf_list):
    if(uf_list[par] < 0): return par
    else:
        uf_list[par] = find(uf_list[par], uf_list)
        return uf_list[par]

def union(f, t, uf_list):
    from_ = find(f, uf_list)
    to = find(t, uf_list)

    if(from_ < to):
        uf_list[to] = from_
    else:
        uf_list[from_] = to

def calc_Euclidean_distance(x1, y1, x2, y2):
    x = x1 - x2
    y = y1 - y2

    return sqrt(x**2 + y**2)

fields = [[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6], [7, 7], [8, 8]]
node = 8
result = 0
hqueue = list()
uf_list = [-1] * 8
edge_count = 0

for i in range(node-1):
    for j in range(node):
        distance = calc_Euclidean_distance(fields[i][0], fields[i][1], fields[j][0], fields[j][1])
        heapq.heappush(hqueue, (distance, i, j)) # 우선순위 큐를 이용해서 가장 거리가 짧은 순서대로 꺼내기

while hqueue:
    distance, from_, to = heapq.heappop(hqueue)

    f = find(from_, uf_list)
    t = find(to, uf_list)

    if(f == t):
        continue

    union(from_, to, uf_list)
    result += distance
    edge_count += 1


print("minimum distance :", result) # sqrt(98) = 9.899494936611667 
print("count of edges :", edge_count)

 

우선순위 큐를 이용해서. 가장 거리가 짧은 순서대로 차례대로 꺼낼 수 있게 했습니다. 나머지는 위에서 이미 설명했듯이. Union-find 를 이용해 싸이클을 체크하고 연결합니다. 이 과정을 반복하면 다음과 같은 결과를 얻을 수 있습니다.

 

 

마치면서

언제나 피드백은 환영입니다. 긴글 읽어주셔서 감사합니다. 혹시 알고싶으신 알고리즘이 있으시다면 댓글로 남겨주세요~~