[파이썬으로 배우는 알고리즘] 최소 신장 트리(MST)

신장 트리

신장 트리(Spanning Tree)란 그래프 내의 모든 노드를 포함하면서 사이클(Cycle)이 없는 부분 그래프를 의미합니다. 이때 모든 노드를 포함하면서 사이클이 없다는 조건은 트리의 성립 조건이기도 하기 때문에 트리라고 불립니다.

 

2022.07.04 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 그래프(Graph)

[파이썬으로 배우는 자료구조] 그래프(Graph)

2022.07.08 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 트리(Tree)

[파이썬으로 배우는 자료구조] 트리(Tree)

 

그림으로 예를 들어보겠습니다.

 

위와 같은 그래프에서 신장 트리는 모든 노드를 포함하면서 사이클이 없는 부분 그래프이므로

 

이와 같이 여러 가지 신장 트리가 나올 수 있습니다. 사이클이 없고 모든 노드를 포함하므로 노드의 개수가 n개일 때 간선의 개수는 n-1개입니다.

 

---

최소 신장 트리

위에서 신장 트리(Spanning Tree)에 알아봤는데 그렇다면 최소 신장 트리는 무엇일까요?

바로 간선에 가중치가 있는 가중치 그래프에서 신장 트리를 이루는 간선의 가중치의 합이 최소가 되는 신장 트리를 최소 신장 트리(Minimum Spanning Tree)라고 합니다. 

 

그래프가 위와 같이 가중치 그래프이고, 신장 트리를 구했을 때 모든 신장 트리를 구하진 않았지만 가운데 있는 신장 트리가 신장 트리 중에서 가중치의 합이 가장 작기 때문에 해당 그래프에서 최소 신장 트리가 됩니다.

 

---

최소 신장 트리의 사용 사례

 

네트워크	라우팅 경로 최적화
도로 건설	모든 도시를 연결하면서 길이가 최소가 되도록 최적화
배관	모든 파이프를 연결하면서 파이프의 총 길이가 최소가 되도록 최적화
전기 회로	모든 전기 회로를 연결하면서 전선 길이가 최소가 되도록 최적화

 

---

최소 신장 트리의 구현

크루스칼(Kruskal) 알고리즘

크루스칼 알고리즘은 그리디 알고리즘을 기반으로 최소 신장 트리를 구하는 대표적인 알고리즘입니다. 

바로 간선의 가중치가 작은 것부터 하나하나 그래프에 포함시켜서 그래프가 신장 트리가 되면 최소 신장 트리가 되는 것입니다!

 

하지만 무작정 작은 가중치의 간선부터 포함시킬 경우 사이클을 형성하는 그래프가 될 수 있으므로 사이클을 형성하는 간선은 포함시키면 안 됩니다.

 

그래프가 위와 같은 가중치를 갖고 있다고 가정하고 크루스칼 알고리즘을 적용하여 최소 신장 트리를 구해보겠습니다.

 

가중치가 작은 순으로 간선을 추가해야 하므로 가중치가 1인 간선을 선택합니다.

 

다음으로 가중치가 작은 가중치가 2인 간선을 선택합니다.

 

가중치가 3인 간선이 가중치가 다음으로 작지만, 사이클을 형성하므로 해당 간선은 선택하지 않습니다.

 

다음으로 가중치가 작은 가중치가 4인 간선을 선택합니다.

 

다음으로 가중치가 작은 가중치가 5인 간선을 선택합니다.

 

간선의 개수가 4개(노드의 개수 - 1)이므로 가중치의 합이 1 + 2 + 4 + 5 = 12인 최소 신장 트리를 만들고 종료합니다.

 

자2022.07.29 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 크루스칼(Kruskal) 알고리즘

[파이썬으로 배우는 알고리즘] 크루스칼(Kruskal) 알고리즘

 

---

프림(Prim) 알고리즘

프림 알고리즘도 크루스칼 알고리즘과 같이 그리디 알고리즘을 기반으로 한 알고리즘이지만, 간선을 중심으로 최소 신장 트리를 구하는 크루스칼 알고리즘과 달리 노드를 중심으로 최소 신장 트리를 구합니다.

 

임의의 노드를 선택하여 그래프를 만들고 해당 그래프와 연결되어 있는 노드 중 가장 작은 가중치의 간선으로 이어진 노드를 선택하여 그래프에 포함시킵니다. (연결된 노드 중에서 이미 그래프에 포함되어있는 노드는 연결된 노드에서 제외)

 

그래프가 위와 같은 가중치를 갖고 있다고 가정하고 프림 알고리즘을 적용하여 최소 신장 트리를 구해보겠습니다.

(시작 노드 1)

 

노드 1을 그래프에 포함시킵니다. 노드 1을 포함한 그래프와 연결되어 있는 노드는 2, 3, 4 노드입니다.

 

노드 2와 연결된 간선의 가중치가 1로 제일 작으므로 노드 2를 그래프에 포함시킵니다. 노드 1, 2를 포함한 그래프와 연결되어 있는 노드는 3, 4, 5 노드입니다.

 

노드 4와 연결된 간선의 가중치가 2로 제일 작으므로 노드 4를 그래프에 포함시킵니다. 노드 1, 2, 4를 포함한 그래프와 연결되어 있는 노드는 3, 5 노드입니다.

 

노드 3과 연결된 간선의 가중치가 4로 제일 작으므로 노드 3을 그래프에 포함시킵니다. 노드 1, 2, 3, 4를 포함한 그래프와 연결되어 있는 노드는 5 노드입니다.

 

노드 5를 그래프에 포함시킵니다.

 

 

노드의 개수가 5개이므로 가중치의 합이 1 + 2 + 4 + 5 = 12인 최소 신장 트리를 만들고 종료합니다.

 

2022.07.30 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 프림(Prim) 알고리즘

[파이썬으로 배우는 알고리즘] 프림(Prim) 알고리즘