[자료구조] 최소비용 신장트리(MST, Minimum cost Spanning Tree)
: 신장트리의 경로에 가중치가 주어져 있을 때, 최소의 비용으로 모든 정점을 연결하는 트리. ※ 신장트리니까 사이클X, n-1개의 경로(간선, 이하 경로라 함)를 가짐 * 최소비용 신장트리를 생성하는 알고리즘 : 크루스칼(Kruskal) 알고리즘, 프림(Prim) 알고리즘 1. 크루스칼 알고리즘(Kruskal's algorithm): 그래프 내에서 최소의 가중치를 가지는 경로를 선택하여 MST를 구성 (MST는 최소비용 신장트리임, 트리 구성중 여러개의 MST가 생기나 결국 하나로 합쳐짐. 신장트리니까!) - 사이클 안됨 (신장트리라고!!) - 이미지에서 볼 수 있듯, 비용이 최소면 사이클이 형성되지 않는 한 무조건 연결(이미지 출처 : http://serverbob.3x.ro/IA/DDU0137.htm..
2017.03.05