[Algorithm] Spanning Tree 와 MST, 스패닝 트리와 최소 스패닝 트리

Spanning Tree 란?

Spanning Tree 란 스패닝 트리라고 읽으며 다른 말로 신장트리 라고도 합니다. 이는 그래프 내의 모든 정점을 포함하는 트리를 말합니다. 그래프의 일부 간선을 이용해 만든 트리로서 항상 그래프의 부분집합이 됩니다.

 

Spanning Tree 의 특징

Spanning Tree 는 이름에서도 알 수 있듯이 트리 중 하나이기 때문에 트리의 특징은 모두 포함합니다.

• 하나의 그래프에는 여러 Spanning Tree 를 가질 수 있습니다.
• 모든 정점을 포함하고 사이클은 생기면 안되기 때문에 N 개의 노드에 대해서 정확하게 N-1 개의 엣지를 가지게 됩니다.

 

MST 란?

MST 란 Spanning Tree의 한 종류로서 사용되는 간선의 가중치 합이 최소인 트리를 말합니다. 이 때 조심해야 할 점은 간선의 수가 최소라고 해서 최소비용은 아닙니다.

 

MST 구현

MST 를 구현하는데 있어서 몇 가지 알고리즘이 있습니다. 그 중에서 대표적인 2가지를 알아보도록 합시다.

• Kruskal 알고리즘

  ssungkang.tistory.com/entry/Algorithm-Kruskal-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

• Prim 알고리즘

  ssungkang.tistory.com/entry/Algorithm-Prim-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[Algorithm] Kruskal 알고리즘

[Algorithm] Prim 알고리즘

 

 

 

MST 의 활용

MST 는 실제 실생활에서 많이 쓰이는 중요한 개념입니다. 실생활을 그래프로 나타낼 수 있을 경우, 각 노드를 연결하는 최소 비용을 구하는 경우라면 말이죠.

대표적으로 각 도시를 모두 연결하는 최소 도로, 각 단자를 모두 연결하는 최소 케이블 망 등 여러 분야에서 중요하게 사용되고 있습니다.