크루스칼 알고리즘(Kruskal's algorithm)

크루스칼 알고리즘란?

크루스칼 알고리즘은 주어진 그래프에 대한 최소 스패닝 트리를 생성하는 데 사용되며 그리디 부류로 작동한다.

 

---

 

그럼 잠깐, 최소 스패닝 트리란 정확히 무엇알까?

최소 스패닝 트리는 그래프와 꼭짓점 수가 같고 꼭짓점 수가 -1인 그래프의 부분 집합이다.

(또한 스패닝 트리의 모든 에지 가중치 합계에 대한 최소 비용도 있다.)

 

그럼 다음으로,

크루스칼 알고리즘은 어떻게 작동할까 ?

1. 모든 에지를 에지 가중치의 오름차순으로 정렬하고,

2. 선택한 에지가 어떤 사이클을 형성하지 않는 경우에만 트리에 노드를 계속 추가한다.

3. 처음에는 최소 비용으로 에지를 선택하고, 마지막으로 최대 비용으로 에지를 선택한다.

다시금 말하면 

모든 최소 결과를 찾기 위해 국소적으로 최적의 선택을 한다고 말할 수 있다.(탐욕 알고리즘이라고 불리는 이유) 

 

---

말로는 힘들 수 있으니 아래 그림을 참고하자. 

a,b,c,d,e 글자 가 있다. 

각 노드들의 엣지중 가장 비용이 작은 순으로 연결 중이며, 싸이클이 생길 시 사용하지 않고 다음 노드를 통해 연결하여

모든 노드들끼리 최소비용으로 연결되도록 한다. 

 

---

 

코드로 이해하자. 

1922번: 네트워크 연결

import sys

input = sys.stdin.readline


def find(a):
    if a == parent[a]:  
        return a
    parent[a] = find(parent[a])  

    return parent[a]


def union(a, b):
    a = find(a)
    b = find(b)
    if b < a:
        parent[a] = b
    else:
        parent[b] = a


n = int(input())
m = int(input())
arr = []
parent = [i for i in range(n + 1)]
res = 0
for i in range(m):
    a, b, c = map(int, input().split())
    arr.append((c,a,b,))

arr.sort(key=lambda x: x[0])
for dis, a, b in arr:
    if find(a) != find(b): 
        union(a, b)
        res += dis
print(res)

여기서 arr.sort(key = lambda x : x[0]을 통해 최소 비용순으로 모든 간선을 연결하고 있다.

find로 부모노드가 다를(다른그룹) 경우에 union함수로 합병하는 코드다.