[Algorithm] 최소신장트리(MST)

[Algorithm] 최소신장트리(MST)

신장트리

n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선들로 이루어진 트리

최소신장트리(MST, Minimum Spanning Tree)

무향 가중치 그래프에서 신장트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

Prim Algorithm

Kruskal Algorithm

Reference

『IT CookBook, 자바로 배우는 쉬운 자료구조』, 이지영 집필, 한빛아카데미(2008)

『 SW 문제해결 응용 - 구현 - 그래프의 최소 비용 문제』