[알고리즘]크루스칼(Kruskal) 알고리즘, 최소 신장 크리(MST)

suhyun·2023년 1월 25일
0

알고리즘 정리

목록 보기
3/5
post-thumbnail

크루스칼 알고리즘

정점(vertex), 가중치가 포함된 간선(edge)로 구성된 그래프가 존재할 때,
그래프의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용

그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때,
가중치의 합이 최소가 되는 상황을 구하고 싶을 때 사용

즉, 최소 신장 트리를 구하기 위한 알고리즘이다.


신장 트리(Spanning tree)와 최소 신장 트리

신장 트리(Spanning tree) 란?

1. 그래프에서 모든 정점 포함
2. 정점 간 서로 연결이 되며, 사이클 존재하지 않음

예를 들어, 아래와 같은 그래프가 존재한다면,

이 그래프에서 나올 수 있는 여러개의 신장 트리 중 일부는 아래와 같다.
왼쪽 그래프의 가중치는 16(1+6+4+5),
오른쪽 그래프의 가중치는 13(1+2+6+4) 이다.

이러한 신장 트리들 가운데, 가중치가 최소가 되도록하는 신장 트리가 최소 신장 트리(Minimum Spanning Tree, MST)이다.

위 그래프의 최소 신장 트리는 아래의 경우이고, 가중치는 10(1+2+3+4) 이다.


알고리즘 진행 과정

크루스칼 알고리즘은 그리디 알고리즘의 일종이다.

즉, 그래프 간선들을 가중치의 오름차순으로 정렬해 놓은 뒤,
사이클을 형성하지 않는 선에서 정렬된 순서대로 간선을 선택 합니다.

① 그래프 간선들을 가중치의 오름차순으로 정렬

② 가중치 순서대로 간선 선택

위의 그래프의 경우에는 사이클이 형성되지 않고 최소 신장 트리를 구할 수 있지만,
아래의 경우에는 ②의 과정 중 사이클이 형성된다.

이런 경우에는 (4-5) 간선이 아닌 (3-5) 간선을 선택하면 사이클이 형성되지 않기 때문에 (3-5) 간선을 선택한다.

선택된 간선의 갯수 = 정점의 갯수 - 1 이 되면 종료


사이클을 찾는 방법

각 정점의 부모 노드 (root node) 를 표현한 parent 배열 생성
자기 자신을 루트 노드로 가지게 초기화 -> parent[i] = i

비교 정점들의 루트 노드를 비교해 사이클의 유무 파악 가능

① 가중치의 순서대로 선택

오름차순으로 정렬된 가중치의 순서대로 (1-2) 를 선택한다.
1과 2가 같은 집합으로 Union 연산에 의해 합쳐진 것이기 때문에, 2의 루트 노드가 1로 바뀐다.

*Union: 서로 다른 두 집합을 병합

위와 같은 과정을 반복한다.

② 사이클이 형성된다면?

Union 연산에 의해 두 점이 합쳐질 수 있는 이유는 두 정점의 루트 노드가 달라서이다.
하지만 아래의 경우에는 4와 5의 루트노드가 동일하다.
즉, 루트 노드가 동일하다는 것은 사이클을 형성한다는 것이기 때문에 Union 연산은 하지 않는다.

최종적으로 parent 배열의 값과 집합 관계는 아래와 같다.

profile
꾸준히 하려고 노력하는 편 💻

0개의 댓글