Spanning Tree

2019.09.23 

 

스패닝 트리 (Spanning Tree)

정의: 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프

 

이때 스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야 함

즉 선택된 간선들이 사이클을 이루지 않는다는 의미임

 

출처 : https://commons.wikimedia.org/wiki/File:Minimum_spanning_tree.svg

위 그림과 같은 그래프가 주어졌을 때, 굵게 표시된 선을 스패닝 트리라고 함

이때, 스패닝 트리는 유일하지 않음. 굵게 표시된 선 뿐 아니라 다른 선들도 스패닝 트리가 될 수 있음(사이클을 이루지만 않는다면)

 

- 문제 유형

최소 스패닝 트리(Mininmum Spanning Tree) 

 : 가중치의 합이 가장 작은 트리 찾기

 

 

스패닝 트리를 푸는 유명한 알고리즘은 아래 두 가지이다.

1. Kruskal

  그래프의 모든 간선을 기준으로 가중치를 작은 순으로 정렬한 뒤,

  스패닝 트리에 하나씩 추가. 이때 스패닝 트리가 사이클을 이룰 경우 해당 간선은 고려대상에서 제외해야 함.

 

  - 풀이방법

  1) 간선을 가중치 오름차순으로 정렬

  2) 간선 목록을 순회하며 스패닝 트리에 추가

      이때, 추가할 간선이 사이클을 이룰 경우 해당 간선은 제외

  

그렇다면 간선이 사이클을 이루는지는 어떻게 판단하는가?

  => 간선 추가하기 전, 간선의 시작점과 끝점 부모가 동일할 경우 사이클을 이룬다고 판단할 수 있음

       즉 Union-find 알고리즘을 통해 추가할 간선의 부모가 동일한지 판단할 수 있음

 

- 구현

 

2. Prim

   추후 학습 예정