MST(Minimum Spanning Tree) 알고리즘이란?

#MST알고리즘 #MST #개발자의도구들

​

AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다

\* 하루 1코테 도전중에 있습니다. 어떤건지 궁굼하신 분들은 여기를 눌려주세요.

MST란?

Minumum Spanning Tree

MST는 Minimum Spanning Tree의 약자로, 최소값을 가지는 Spanning Tree입니다. MST를 알기위해선 Spanning Tree에 대한 개념을 알고 있어야하는데, 그전에 Tree와 Graph의 차이를 먼저 확실히 알고 가는 것이 좋습니다.

​

목차

Graph vs Tree

Spanning Tree

Minimum Spanning Tree

Graph vs Tree

그래프는 일반적으로 생각하기 쉬운 노드와 간선들의 집합입니다.

​

그래프를 좀 더 일반적이고 범위가 넒은 개념으로 생각하시면, 특징을 이해하기가 쉽습니다. 그래프는 방향이 있을수도, 없을수도 있으며, 노드사이에 부모 - 자식이라는 개념이 없습니다. 또한 순환도 가능합니다. 노드와 노드사이 경로 역시 여러개가 가능합니다.

​

이전에 Dikjstra알고리즘과 floyd-warshall에서 Graph를 이용하는 이유도, 길을 찾는 것에 있어서, 우위가 없으며, 길은 순환 가능하고, 경로 역시 다양하게 존재하기 때문입니다.

​

반면에, Tree는 세부적인 특징이 존재합니다. Tree는 그래프의 일부이기 때문에, 포괄적인 그래프의 개념에서 세부적으로 구분되는 것은 당연합니다.

​

Tree는 방향을 반드시 가지며, 두 노드 사이에 부모 - 자식의 관계가 성립합니다. 방향은 무조건 부모에서 자식으로 향해야 하며, 반드시 하나의 경로를 가져야 합니다. 따라서 순환이 불가능한 구조입니다.

​

위 개념을 제대로 잡고 공부하지 않아서, 알고리즘에 구현에 많이 헤맸습니다... 여러분들은 위 두 개념을 명확히 잡으시고 공부하시길 추천드립니다!

Spanning Tree

이제 본격적으로 Spanning Tree에 대해 알아봅시다. Spanning Tree는 그래프내의 모든 정점을 포함하는 트리입니다. 정점을 모두 포함한다는 조건이 있기 때문에, 노드와 간선의 수는 정해진 공식을 따릅니다.

​

Spanning Tree 노드수 = 그래프의 노드 수, Spanning Tree의 간선의 수 = 그래프의 노드수 - 1

​

위의 그래프에서 SpanningTree를 만들어 보겠습니다.

​

SpnningTree의 조건만 만족하면 되기 때문에 여러개의 Spanning Tree가 만들어집니다.

MST : Minimum Spanning Tree

Spanning Tree에서 사용하는 그래프의 간선에 가중치를 추가해 봅시다.

그러면 위에서 구한 각 Spanning Tree의 가중치도 구할 수 있습니다.

tree1 / tree2

tree3/ tree4

각 Spanning Tree의 가중치의 합을 구해봅시다. tree1 = 14, tree2 = 18, tree3 = 16, tree4 = 10입니다. 같은 Spanning Tree이지만, 가중치가 차이나는 것을 볼 수 있습니다.

​

MST는 Spanning Tree에서 가장 적은 가중치를 가지는 Spanning Tree입니다. 위의 경우에서는 tree4가 되겠습니다.

​

MST를 구하는 방법

사실 위의 그래프에서 표현하지 않은 Spanning Tree가 존재합니다. 하지만, 제가 tree4가 MST라고 단정지어 말을하였습니다. 그 이유는 전체 Spanning Tree를 구하지 않아도 MST를 구할 수 있기 때문입니다.

​

사실 Spanning Tree를 구하는 것 자체는 별로 쓸일이 없습니다. 그래프를 활용할 때는 항상 최솟값이 얼마인지가 중요한 부분이기 때문에, 모든 Spanning Tree를 구하는 것보다, 최소의 Spanning Tree를 구하는 방법이 더 중요합니다.

​

Spanning Tree를 구하는 방법에는 크게 3가지 알고리즘이 있습니다.

​

1. Kruskal 알고리즘

1. Prim 알고리즘

1. Boruvka

​

특히 1,2 번은 MST에서 가장 많이 사용되는 알고리즘 이기 때문에 다뤄볼 예정이고, 3번은 여유가 된다면 다뤄보겠습니다.