PLOD

MST하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하다. 최소 길이의 간선으로 모든 노드들을 연결해야 되는 문제가 나올 때 최소 신장 트리 알고리즘을 사용 할 수 있다.Kruskal Algorithm크루스칼 알고리즘은 대표 적인 최소 신장 트리 알고리즘이다. 크루스칼 알고리즘은 greedy algorithm(탐욕 기법)에 속한다. 먼저 모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시키면 된다.  Kruskal 알고리즘은 간선을 정렬하는데 시간이 가장 오래 걸리기 때문에 간선의 개수가 E 일때, O(ElogE)의 시간 복잡도..