[알고리즘] 최소 스패닝 트리 (MST, Minimum Spanning Tree)

최소 스패닝 트리 / 최소 신장 트리 (MST, Minimun Spanning Tree)

스패닝 트리 / 신장 트리는 모든 정점(Vertex, Node)을 간선(Edge)로 사이클이 생기지 않게 연결한 그래프입니다.

최소 스패닝 트리 / 최소 신장 트리는 신장 트리 중에서도 간선의 총 비용이 최소가 되는 트리 입니다.

 

 

 

 

 

각 노드와 노드간의 간선이 위와 같이 주어졌습니다.

그럼, 이 위 그래프에서 모든 노드가 이어져 있으면서, 간선의 합이 최소가 되려면 어떤 간선을 선택해야 할까요?

 

 

 

빨간색으로 칠한 간선들을 선택한다면, 간선의 비용을 최소로 하면서 모든 노드를 연결할 수 있습니다.

위 형태가 해당 그래프의 최소 스패닝 트리가 됩니다.

 

물론, 그래프에 따라 비용이 최소가 되는 스패닝 트리는 여러개 있을 수 있기에,

최소 스패닝 트리는 두 개 이상 존재할 수 있습니다.

 

이러한 최소 스패닝 트리를 구하는 데에는 프림 알고리즘, 크루스칼 알고리즘, 솔린 알고리즘이 있는데

주로 프림과 크루스칼 알고리즘을 사용합니다.

 

 

 

크루스칼(Krustal) 알고리즘

크루스칼(표기/읽는법에 따라 크러스컬) 알고리즘은 탐욕법(그리디, Greedy)에 기초한 알고리즘입니다.

간선을 비용이 적은 순으로 정렬하고, 비용이 적은 간선부터 사이클이 생기지 않도록 차례로 하나씩 선택해나가며

최소 스패닝 트리를 찾는 알고리즘입니다.

 

 

 

위 그래프를 크루스칼 알고리즘을 사용해 최소 스패닝 트리를 찾아봅시다.

(실제 지역 위치와 이동시간을 고려해 만들려 했으나,,, 쉽지 않아 그냥 막 만들었습니다 ㅠㅠ,,,,)

 

 

 

간선 중 가중치가 가장 작은 간선을 찾아봅시다. 성남 - 용인 간선이네요. 두 노드를 이읍니다.

(가중치가 같은 간선이 여러개일 경우 아무거나 선택해도 무방합니다.)

 

 

 

다음으로 간선의 비용이 적은 걸 찾아봅시다.

서울 - 수원 간선입니다. 두 노드를 이어줍니다.

 

 

그 다음 순서는 성남 - 강릉입니다. 가중치가 4입니다.

 

 

 

가중치가 5인 간선은 두개가 있습니다. 가중치가 동일 한 간선이 여러개 있을 경우 아무거나 선택해도 무방합니다.

강릉 - 용인 간선을 선택해봤습니다. 하지만 두 간선을 이을 경우 사이클이 발생하게 됩니다.

다른 간선을 찾아봅시다.

 

 

 

수원 - 용인 간선을 이었습니다.

 

 

 

파주 - 강릉 간선도 5네요. 이것도 이어봅시다.

 

 

 

그 다음 간선은 천안 - 파주 간선으로, 가중치가 6입니다.

이로써 모든 간선이 다 이어지면서(스패닝 트리), 그 비용이 최소인 형태(최소 스패닝 트리)를 찾았습니다.

 

사이클의 유무는 분리집합과 유니온 파인드 (Union - Find)을 사용하여 판단할 수 있습니다.

분리집합 알고리즘은 아래 포스팅을 참고해주세요.

https://uknowblog.tistory.com/61

[자료구조] 분리 집합(Disjoint set)과 유니온 - 파인드(Union-Find)

 

 

 

 

프림(Prim) 알고리즘

이번엔 프림 알고리즘을 살펴봅시다.

크루스칼은 간선 중심이였다면, 프림은 정점 중심이라는 느낌을 받았습니다.

 

첫 번째로 임의의 정점 하나를 선택하여,  (n-1)개의 간선을 하나씩 추가시켜 만드는 방법으로,

연결된 간선 중 비용이 최소인 것을 선택하는 것을 반복하는 형태입니다.

프림 알고리즘도 그리디에 기반을 두고 있다 할 수 있겠네요.

 

매 노드를 탐색할 때마다, 노드에 연결된 간선이 추가됩니다.

따라서 매 노드를 탐색할 때마다 정렬을 해야하기 때문에

우선순위 큐가 유용하게 쓰입니다.

 

 

 

시작점이 될 노드를 선택합니다. 모든 간선이 스패닝 트리에 포함이 될 것이므로, 시작 노드로 어떤 노드를 선택해도 무방합니다.

우선순위 큐에 성남 - 용인 간선, 수원 - 용인 간선, 용인 - 강릉 간선을 넣습니다.

 

현재 우선순위 큐 : 용인 - 성남 (1), 수원 - 용인 (5), 강릉 - 용인(5)

우선순위 큐에서 (비용이 가장 적은) 간선 하나를 꺼냅시다. 성남 - 용인 간선입니다.

여기서 우선순위 큐는 비용 오름차순 기준으로 정렬합니다.

 

 

 

성남 - 용인 간선을 이었습니다.

성남에 연결된 간선인 성남 - 강릉 간선을 우선순위 큐에 넣습니다.

 

현재 우선순위 큐 : 성남 - 강릉 (4), 수원 - 용인 (5), 강릉 - 용인(5)

우선순위 큐에서 하나를 꺼내봅시다. 성남 - 강릉 간선입니다.

 

 

 

성남 - 강릉 간선을 이어줬습니다. 강릉에 연결된 간선을 우선순위 큐에 넣습니다.

강릉 - 용인 간선은 이미 있으므로 제외합니다.

 

현재 우선순위 큐 : 강릉 - 용인(5), 파주 - 강릉(5), 수원 - 용인 (5)

우선순위 큐에서 하나를 꺼내봅시다.

가중치가 여러개일 경우, 아무거나 선택해도 무방합니다. 어차피 모든 노드는 스패닝 트리에 포함되기 때문입니다.

강릉 - 용인 간선입니다. 하지만 용인은 이미 방문했으므로 하나 더 큐에서 꺼냅니다.

파주 - 강릉 (5) 간선입니다.

(방문체크는 그냥 Boolean 배열로 체크하여도 됩니다.)

 

 

 

파주 - 강릉 간선을 이었습니다. 마찬가지로 연결된 간선들을 우선순위 큐에 넣어줍니다.

현재 우선순위 큐 : 수원 - 용인 (5), 파주 - 천안 (6), 파주 - 서울(7)

하나를 꺼냅니다. 수원 - 용인 간선입니다.

 

 

 

현재 우선순위 큐 : 수원 - 서울(2), 파주 - 천안 (6), 파주 - 서울(7), 천안 - 수원(8)

수원에 연결된 간선들을 우선순위 큐에 넣고, 하나를 꺼냅니다. 이번 여행지는 수원 - 서울(2) 입니다.

 

 

 

서울에 연결된 간선은 서울 - 파주 입니다.

파주는 이미 방문했으므로 우선순위 큐에 넣지 않아도 됩니다.

 

현재 우선순위 큐 : 파주 - 천안 (6), 파주 - 서울(7), 천안 - 수원(8)

큐에서 하나를 꺼냅니다. 파주 - 천안 (6) 입니다. 벌써 마지막 여행지네요.

 

 

 

이로써 모든 노드가 서로 연결되면서, 비용이 최소인 형태를 찾았습니다.

위 그래프의 경우, 크림과 크루스칼 알고리즘으로 구한 최소 스패닝 트리가 같은 형태이지만,

 

최소 스패닝 트리는 모든 노드 연결 + 가중치 합이 최소인 그래프이므로, 최소 스패닝 트리는 복수개가 될 수 있습니다.

복수개일 경우, 크림과 크루스칼로 구한 트리 형태가 서로 다를 수 있으나,

특정 모양의 트리를 구하는 것이 목적이 아니라면 별 상관 없습니다.

 

 

후기

지금까지 최소 스패닝 트리의 개념과, 구하는 방법을 알아봤습니다.

최소 스패닝 트리 알고리즘은 망 형태의 네트워크, 전화선, 케이블 TV 선 등 여러 통신용 선이나

배수로, 가스관, 혹은 철도 등에도 응용할 수 있습니다.

 

처음 최소 스패닝 트리를 접했을 때, 매우 혼란의 연속이였습니다.

 

알고리즘과 코테를 처음 공부할 때, 백준에서 문제 하나를 풀다가, 이거를 도대체 어떻게 풀지...?? 하는 마음에 질문 게시판을 들어갔다가,

최소 스패닝 트리를 사용해 풀어야 한다는 글을 보고 최소 스패닝 트리를 구글링 해봤습니다.

 

아 이 문제 도대체 어떻게 풀어야 하지...??? -> 최소 스패닝 트리를 사용해 푸시면 되요!

최소 스패닝 트리는 뭐지? -> 스패닝 트리 종류 중 하나인데, 스패닝 트리 중에서도 간선의 합이 최소가 되는 트리에요

스패닝.. 트리... -> 모든 노드가 간선으로 이어져 있으면서 사이클이 없는 트리에요!

흠... 일단 오케. 근데 어떻게 구하지? -> 프림과 크루스칼 알고리즘을 사용해 구할 수 있어요!

크루스칼은 또 뭐지...??? -> 그리디에 기반을 둔 건데, 간선이 적은 것 부터 선택해서 만들어요! 사이클 유무는 분리집합 통해 확인해요!

분리집합???????? -> 서로소 집합인데, 분리집합은 유니온 파인드를 통해 구현할 수 있어요!

유?니?온? 파?인?드? -> 트리 구조에서 노드의 부모를 찾고(Find) 병합하는(Union) 알고리즘이에요

그럼 프림은 뭐지... 아니다... 나중에 봐야지....

 

그러다가, 학과 커리큘럼으로 알고리즘 수업을 듣다가 다시 만난 최소 스패닝 트리.

이번엔 학점이 인질로 잡혀있었기에 제대로 공부해보고 관련 문제도 여러 개 풀어보니 이젠 어느정도 응용할 수 있게 되었습니다.

전공 수업에서 배운 것들이 나오면 상당히 재밌습니다. 이상한거 배운게 아니였네... 하는 느낌.