[Algorithm] 최소 신장 트리 Minimum Spanning Tree

Minimum Spanning Tree(MST) MST(Minimum Spanning Tree)에 대해 알아보기 전에 Spanning Tree가 무엇인지 부터 알아야 한다. Spanning Tree란 1. 그래프의 모든 정점을 포함 2. 간선의 수가 가장 적음(n-1개) 3. 사이클이 없음 인 트리의 특수한 형태이다. 위의 두 조건을 만족하는 경우는 여러가지 이므로 하나의 그래프에는 많은 신장 트리(spanning tree)가 존재할 수 있다. 이는 BFS, DFS를 이용하여 찾을 수 있다. 그렇다면 MST는 무엇일까 MST는 위에서 설명한 spanning tree 중에서 사용된 간선들의 가중치 합이 최소인 트리이다. 각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비..