우선, Spanning Tree는 무엇일까?
그래프 내의 모든 정점을 포함하는 트리를 의미한다.
간선의 수(edges)가 가장 적게, 최소 연결을 해야하는 트리
다시말하자면 그래프에서 일부 간선들로 이루어진 트리를 말한다
앞서 설명한 Spanning Tree 중에서 사용된 간선들의 가중치의 합이 최소인 트리를 의미한다.
모든 정점들을 가장 적은 수의 간선과 가중치의 합으로 연결하는 것이다.
여러 포스팅을 읽어보면서 느낀 점은 비교할 간선이 많은 경우에는 Prim 알고리즘을, 간선이 비교적 적은 경우에는 Kruskal을 사용해서 해결한다고 한다. 그 외 다익스트라와 같이 지점 to 지점으로 최소의 가중치를 가지고 있는 path를 찾아낼 수도 있지만 이번 포스팅에서는 많이 다뤄지는 Kruskal과 Prim에 대해서 다뤄보고자한다.
생각보다 신기했던 알고리즘, Union과 Find의 조화
예를 들어서 아래와 같은 그래프가 있다고 해보자
총 정점은 모두 5개로 정점마다 a,b,c,d,e 라고 이름이 붙어져 있으며 간선 위에는 각 가중치가 적혀있다. 이때 가중치를 기준으로 오름차순 정렬을 해보면 아래와 같이 정렬할 수 있다.
가중치 | 간선 |
---|---|
1 | a-b |
1 | c-e |
2 | c-d |
3 | a-d |
4 | a-c |
4 | d-e |
형성된 스패닝 트리가 없다면 가장 위에 있는 a-b 간선을 트리에 추가해준다. 그리고 다음으로 가중치가 작은 간선은 c-e가 되는데, 이때 c-e간선이 사이클을 만드는지 확인을 해야한다.
그렇다면 사이클을 형성하는지는 어떻게 알 수 있을까? Union-Find 자료구조를 사용하면 된다.
Union-Find 자료구는 Disjoint Set(서로소 집합, 공통원소가 없는 두 집합)을 표현하는 자료구조이다.
두 집합을 먼저 병합을 한다고 해서 Union, 그리고 집합 원소가 어디에 속해있는지 찾는다고 해서 Find이다.
Union-Find를 통해서 사이클을 형성하는 지 알아보자!
먼저, 스패닝 트리가 형성되기 전인 상황으로 돌아간다고 가정을 하고 parent 배열을 만들어 본다
child | a | b | c | d | e |
---|---|---|---|---|---|
parent | a | b | c | d | e |
위와 같이 생긴 서로소 집합을 만들 수 있다. 간선을 선택하기 전인 위에 배열은 각자의 부모를 본인으로 설정해둔 것이다.
child | a | b | c | d | e |
---|---|---|---|---|---|
parent | a | b→a | c | d | e |
b의 부모가 a로 바뀌었다.
바꿔준 이유는 뭘까? a와 b가 서로 각자 다른 노드를 가리키고 있었고, 이 상황에서 a-b 간선을 선택해줬기 때문에 a와 b는 이제 같은 집합 내 속해있다고 값을 변경해주어야한다. 그러므로 각자 다른 부모 노드를 가리키고 있을 때 두개의 노드 모두 작은 값을 가진 부모를 가리키게 하므로 같은 집합 내 속하게 만드는 것이다.
✨ 각자 가리키는 부모가 다를 때, 작은 값의 부모로 통일시켜준다.
이렇게 되면 그래프가 아래와 같이 구분 지어 질 수 있다.
그룹 1 | 그룹 2 | 그룹 3 | 그룹 4 |
---|---|---|---|
a, b | c | d | e |
child | a | b | c | d | e |
---|---|---|---|---|---|
parent | a | a | c | d | e→c |
...
계속해서 같은 작업을 반복하게되면 마지막에는 아래와 같은 표와 함께 탐색이 종료된다.
child | a | b | c | d | e |
---|---|---|---|---|---|
parent | a | a | c | c→a | c |
탐색이 종료되는 이유는 연결된 간선의 갯수가 모든 정점의 갯수 - 1개와 같기 때문이다.
만약에 간선 d-e가 가중치 3을 갖고 있었다면, a-d보다 우선순위가 높았을 것이며 아래와 같이 그래프가 이루어졌을 것이다.
가중치 | 간선 |
---|---|
1 | a-b |
1 | c-e |
2 | c-d |
3 | d-e |
4 | a-d |
4 | a-c |
이때는 parent 배열이 아래와 같이 되어있을텐데,
child | a | b | c | d | e |
---|---|---|---|---|---|
parent | a | a | c | c | c |
이때 d와 e를 선택하려고 하면 서로 같은 부모를 가리키고 있기 때문에 사이클이 형성되는 점을 알 수 있다.
🎯 이렇게 간선을 선택할 때 ① 사이클을 형성하는 지 확인 ② 선택한 간선의 갯수가 모든 정점의 갯수 -1 개인지 확인 하면서 작은 가중치를 더해가다보면 Kruskal 알고리즘을 적용해서 문제를 해결할 수 있다.
찾으려는 노드의 부모가 어느 집합에 소속되어있는지를 알아내야하는 게 중요하다.
위와 같이 4의 부모가 2이지만, 2는 또 1에게 속해있기 때문에 이런 점을 주의해야한다. 따라서 while문이나 재귀를 이용해서 잡아주는 것이 좋다.
예시코드)
def find(parent, node):
if parent[node] == node: return node
else: find(parent, parent[node])
지정한 정점부터 출발, 트리를 단계적으로 확장
정점을 선택하면서 이전 단계에서 만든 트리를 확장해나가는 방식
👉 백준-최소 스패닝 트리
👉 백준-네트워크 연결
👉 백준-도시 분할 계획
✨ https://chanhuiseok.github.io/posts/algo-33/
✨ https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html