[자료구조] 신장 트리, 최소 비용 신장 트리 (Spanning Tree)

신장 트리(Spanning Tree)란?

  아래 조건을 만족하는 그래프를 의미합니다.
  1. 연결 그래프의 부분 그래프이며, 그래프에서 모든 정점을 포함합니다.
  2. 정점 간 서로 연결이 되어있어야 합니다.
  3. 사이클이 존재하지 않는 그래프
  4. 연결 그래프에서 신장트리는 1개가 아닌 다수일 수 있습니다.

   아래 그림은 연결 그래프를 다양한 신장트리로 표현한 예입니다.

 

최소 비용 신장 트리(MST - Minimum Cost Spanning Tree)란?

1. 트리를 구성하는 간선들의 가중치를 합한 값이 최소가 되는 신장 트리입니다.

2. 가중치 무방향 그래프가 베이스일때 구할 수 있습니다.

3. MST를 찾아내는 방법은 다양하며 대표적으론 (크루스칼, 프림) 알고리즘이 있습니다.

[크루스칼 알고리즘 정리]
choidev-1.tistory.com/140

 

MST 사용 사례

  전반적으로 서로를 연결하면서 그 길이가 최소가 되도록 하는 문제에 많이 사용 됩니다.

1. 도로 건설 (도시를 모두 연결하고, 도로 길이가 최소가 되도록 하는 문제)

2. 전기 회로 (단자들을 모두 연결하면서 전선의 길이가 최소가 되도록 하는 문제)

3. 통신 (전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제)

4. 배관 (파이프를 모두 연결하면서 파이프의 총 길이가 최소가 되도록 연결하는 문제)