!!개인 공부용이기 때문에 틀린 내용이 있을 수도 있습니다!! 잘못된 내용이 있으면 언제든지 지적해 주세요.
요즘 알고리즘 스터디를 하고 있는데 배우는게 많다
자주 쓰는 알고리즘 말고는 잘 모르는 것도 많고
아무튼 오늘 스터디장님이 설명해 주신 걸 정리해 봐야겠다
MST는 Minimum Spanning Tree의 약자이다. Spanning Tree중에서 간선들의 cost 합이 최소가 되는 경우를 최소 신장 트리, 혹은 MST라고 한다.(Spanning Tree는 최소한의 간선을 사용해서 연결한 트리를 말한다. 정점의 개수가 n이라면, Spanning Tree는 n-1개의 간선으로 연결되어 있다.)
MST를 구현하는 방법에는 Kruskal 알고리즘과 Prim 알고리즘이 있다.
두 알고리즘에 대해서는 다음 게시물에서 설명할 예정이다.
