Minwoo Dev.

Kruskal 알고리즘굉장히 유명한 알고리즘이다.최소비용신장트리(MST, Minimum Spanning Tree)를 찾는 알고리즘이다. 예를 들어 위와 같은 가중치 그래프가 있다고 하자. Prim 알고리즘은 시작 정점이 필요했지만, Kruskal 알고리즘은 시작 정점이 필요하지 않다.Kruskal 알고리즘은 가장 작은 가중치를 갖는 간선을 찾아 여러 개의 작은 트리로 만들어두고, 붙이는 알고리즘이다. 쉽게 풀어서 차근차근 이야기해 보자. 우선, 가장 작은 가중치인 7이 연결된 두 정점을 선택하게된다.그리고 다음으로 작은 가중치인 10이 연결된 정점들을 묶는다. 그 다음으로 큰 12 를 묶는다.Kruskal 알고리즘은 연결되지 않는 게 많을 것이다. 이상해하지 말자. 곧 연결될테니다음으로 큰 13  13이..

최소비용 신장트리(MST, Minimum Spanning Tree)가중치 그래프에서, 간선들의 비용 합이 최소가 되는 신장트리최소비용 신장트리는 그래프가 아니라 트리 이기때문에 사이클이 구성되지 않아야한다.   우선, 최소비용 신장트리가 아니라 일반적인 신장 트리의 모습이 아래에 있다.  위 그림처럼 그래프에서 나올 수 있는 신장트리는 여러 개일 수 있다.  하지만, 일반적인 신장트리와 다르게 최소비용 신장트리는 간선에 가중치가 있기때문에, 그 값에 따라 최소한의 비용으로 나타낼 수 있는 트리여야 한다.   위 사진처럼 각 간선에 가중치가 있고, 그 가중치가 가장 작은 간선으로 이동하는 방식으로 얻은 트리가 최소비용 신장트리, MST이다.   최소비용 신장트리(MST)를 구하는 방법에는 크게 Prim 방..