[알고리즘] 크루스칼 알고리즘(Kruskal Algorithm)

신장 트리 (Spanning Tree)

무방향 그래프의 최소 연결 부분 그래프를 말한다. 즉, N개의 정점을 가지는 그래프 중 모든 정점을 포함하면서 최소 간선의 수인 N-1개의 간선으로 연결된 부분 그래프를 뜻한다. 특정 그래프에서 최소 간선 수인 N-1개의 간선을 가지고 있는 그래프는 트리 형태를 이룰 수 밖에 없어 신장 "트리"라고 한다. 

🔹정점 수: N
🔹간선 수: N-1 
🔹즉, 그래프 내 모든 정점을 포함하는 트리 (사이클 존재 X)

위의 그림과 같이 하나의 그래프에서 신장 트리는 여러개가 존재할 수 있다. 이때 하나의 그래프에서 생성될 수 있는 신장 트리 중 가중치의 합이 가장 작은 트리를 최소 신장 트리라고 한다. MST를 구할 수 있는 알고리즘으로 크루스칼 알고리즘과 프림 알고리즘이 있다.

💡 최소 신장 트리 (MST: Minimum Spanning Tree)
GRANT 데이터베이스 사용자에게 권한을 부여 
REVOKE 데이터베이스 사용자에게 권한을 취소

 

 

크루스칼 알고리즘

그리디한 방법을 이용해 그래프의 모든 정점을 최소 비용으로 연결하며 최적의 해답을 도출하는 알고리즘이다. 하지만 무작정 최소 간선만 선택하다보면 사이클이 발생하며 최소 신장 트리의 특징을 무시해버릴 수 있기 때문에 사이클을 형성하지 않는 최소 비용의 간선을 선택해야 한다. 

1. 그래프의 간선들을 오름차순으로 정렬
2. 정렬된 간선들 탐색하며 MST 집합에 포함 (사이클을 형성하지 않는, 최소 비용의 간선 선택)
    - 선택한 간선이 사이클 형성 → 트리 집합에 포함 X 
    - 선택한 간선이 사이클 형성 X → 트리 집합에 포함
3. 2번 과정을 N-1번 반복 (모든 정점을 연결할 때까지)

 

1. 간선 오름차순 정렬

위와 같이 그래프가 있을 때, 간선의 가중치를 오름차순으로 정렬한다. 여기서 간선 (4,5)는 정점 4와 정점 5를 잇는 간선이라는 의미이다.

 

2. 사이클을 형성하지 않는 최소 비용 간선 선택

가중치가 작은 순서부터 정렬되어 있는 간선 리스트에서 그리디하게 가장 작은 간선을 MST에 포함시킨다. 표에서 MST에 포함시킨 간선은 파란색으로 표시했다.

 

다음 간선을 살피고 사이클이 발생하는지 확인한다. 간선 (1,5)를 포함시켜도 사이클이 발생하지 않으므로 MST에 포함시킨다.

 

간선 (3,4) 역시 포함시켜도 사이클이 발생하지 않으므로 포함시킨다.

 

간선 (1, 3)을 포함시키려고 하니 사이클이 발생하므로 간선(1,3)은 MST에 포함시키지 않는다.

간선(2,3) 까지 포함하고 나니 간선 4개가 포함되었고, 정점이 5개인 그래프에서 최소 간선의 수는 4개이므로 탐색을 종료한다. 이로써 가중치의 합이 14인 최소 신장 트리가 구해졌다.

 

사이클 생성 여부 확인

크루스칼 알고리즘 자체는 사이클 존재 여부를 확인하는 조건 하나와 그리디한 방식으로 비용을 최소화하는 것으로 간단히 이해할 수 있다. 그리디하게 작은 비용부터 탐색하는 방법은 정렬을 통해 구현할 수 있다. 그렇다면 사이클이 생성되는지 확인하는 것은 어떻게 할까? 서로소 집합을 표현하는 방법인 Union-Find 알고리즘을 통해 사이클이 생성되는지 판단할 수 있다.

// union-find 포스팅 링크

Union-Find 알고리즘을 통해 추가하고자 하는 간선의 양 끝 정점이 같은 집합에 속해 있는지를 검사한다.

🔹두 정점이 같은 집합에 속함 → 사이클 생성
🔹두 정점이 각각 다른 집합에 속함 → 사이클 생성 X

 

📒크루스칼 알고리즘 추천 문제
👉 백준 1197 최소 스패닝 트리