ICT 지식) 최소 스패닝 트리(Minimum Spanning Tree)

최소스패닝 트리(Minimum Spanning Tree)는 그리디(Greedy) 알고리즘의 대표적인 예이다.

 

이는 가장 작은 가중치를 가진 간선부터 연결하고 연결중에 사이클이 생기면 무시하면서 모든 노드를 연결해야한다.

 

예를들어 아래와 같은경우 최소 스패닝 트리를 만들어본다고 해보자

 

 

우선 가중치가 제일 작은 간선을 연결한다.

그다음 작은 가중치를 가진 간선 7을 연결한다.

마찬가지로 그다음 작은 가중치를 가진 8을 연결한다.

9는 2개지만 아래쪽의 9를 연결해버리면 삼각형 모양의 사이클이 생기기때문에 위에쪽의 9를 연결한다.

그 다음 10을 연결한다.

마지막으로 12를 연결해준다.

 

그럼 최종적으로 이런 형태가 그려지면서 최소 스패닝트리가 만들어진다.