개발새발 로그

크루스칼 알고리즘 (Kruskal Algorithm) 이란 그래프 내의 모든 정점들을 가장 적은 비용(cost)으로 연결하기 위해 사용되는 알고리즘이다. 즉 최소 비용 신장트리를 만들기 위한 대표적인 알고리즘이다. 예를 들어 각 도시를 도로를 이용해 연결해 모든 도시가 연결되도록 할 때 최소한의 비용을 구하는 것이다. 먼저 신장트리에 대해 알아보자 신장 트리 (Spanning Tree) 이러한 그래프가 있다고 가정하자 이 그래프를 연결하는 최소 연결부분만 사용한다면 아래와 같이 나온다. 더 많은 경우가 있지만 생략했다. 최소 연결이란 간선의 수가 가장 적다는 것을 의미한다. 그래프에서 일부 간선을 선택해서 만든 트리. 모든 정점들이 연결 되어 있어야하고 사이클을 포함하면 안된다. 하나의 그래프에는 여러개..