알고리즘/이론

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

ssung.k 2019. 10. 4. 20:34

Spanning Tree 란?

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

 

Spanning Tree 의 특징

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

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

 

MST 란?

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

 

MST 구현

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

 

[Algorithm] Kruskal 알고리즘

Kruskal 알고리즘이란? Kruskal 알고리즘이란, 그래프에서 MST 를 찾는 알고리즘입니다. MST 가 무엇인지 모르신다면 아래 링크를 참고해주세요. Spanning Tree 와 MST [Algorithm] Spanning Tree 와 MST, 스패닝..

ssungkang.tistory.com

 

[Algorithm] Prim 알고리즘

Prim 알고리즘이란? Prim 알고리즘이란, 그래프에서 MST 를 찾는 알고리즘입니다. MST 가 무엇인지 모르신다면 아래 링크를 참고해주세요. Spanning Tree 와 MST [Algorithm] Spanning Tree 와 MST, 스패닝 트리와..

ssungkang.tistory.com

 

 

 

MST 의 활용

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

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

 

저작자표시