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

: 신장트리의 경로에 가중치가 주어져 있을 때,

   최소의 비용으로 모든 정점을 연결하는 트리.

   ※ 신장트리니까 사이클X, n-1개의 경로(간선, 이하 경로라 함)를 가짐

* 최소비용 신장트리를 생성하는 알고리즘 : 크루스칼(Kruskal) 알고리즘, 프림(Prim) 알고리즘

1. 크루스칼 알고리즘(Kruskal's algorithm)

: 그래프 내에서 최소의 가중치를 가지는 경로를 선택하여 MST를 구성 (MST는 최소비용 신장트리임, 트리 구성중 여러개의 MST가 생기나 결국 하나로 합쳐짐. 신장트리니까!)

 - 사이클 안됨 (신장트리라고!!)

 - 이미지에서 볼 수 있듯, 비용이 최소면 사이클이 형성되지 않는 한 무조건 연결

(이미지 출처 : http://serverbob.3x.ro/IA/DDU0137.html, 끝까지 보고 싶으면 가서 보삼)

2. 프림 알고리즘(Prim's Algorithm)

: 그래프 내에서 한 점을 기준으로 최소의 비용을 가지는 정점을 선택하여 MST를 구성(트리 구성중 MST는 하나밖에 없음)

 - 사이클 안됨(신장트리라니까?)

 - 이미지에서 확인할 수 있듯, 근본이 있는 신장트리임... (아.. 크루스칼이 근본 없다는건 아니고...)

(이미지 출처 : 위와 같음)

* 프림과 크루스칼 알고리즘의 차이

  > 트리 생성중 MST가 하나만 생기느냐 여러개가 생기느냐

  > 마구잡이로 연결하느냐, 한 점에서 연결하느냐

* 결국 생기는 신장트리는 같을 수 있다.