[ 알고리즘 개념 ] 최소신장트리 (Minimum Spanning Tree)
최소신장트리 (Minimum Spanning Tree) 1. 개념 ▷ 신장트리란? - 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 ( 큰 틀에서 트리에 포함되는 조건이다. ) - 즉, 누락된 노드가 존재하거나 사이클이 존재하면 신장트리 조건 위배 - 아래 예시와 같이 한 그래프에 여러 신장트리가 존재할 수 있다. ▷ 최소신장트리란? - 최소한의 비용으로 구성되는 신장트리 예) N개의 도시가 있고, 이 도시 사이에 도로를 놓아 전체 도시가 연결되어야 하는데 이때, 최소 비용으로 연결 위 그림에서 두번째 신장 트리는 총 비용(Cost)이 11이므로 최소 신장 트리가 아니다. 세번째 신장 트리의 비용이 7로 더 작으므로 최소 신장 트리는 세번째이다. 최소 신장 트리 알고리즘에는 대표적..