자료구조 & 알고리즘/최소신장트리 - 프루스칼

[크루스칼 알고리즘]간선을 가중치 순으로 오름차순 정렬하고, 사이클을 검사하면서 최소 신장 트리를 구성하는 간선 중심 알고리즘.간선을 양방향으로 저장할 필요 없이 단방향만 저장해도 충분.사이클 체크 방법 -> 유니온 파인드주로 간선 수가 적을 때 사용O(ElogE) -> 간선 만큼의 정렬 복잡도를 따라감cf) 크루스칼, 프림 모두무방향 그래프를 대상-> 프림은 노드 중심 알고리즘이기 때문에 간선 양방향 저장public class Main { static int parents[]; public static int example(int[][] data, int v, int e) { int weightSum = 0; parents = new int[v + 1]; ..