최단 경로 알고리즘 - 최소신장트리 (Minimum Spanning Tree)
최소신장트리 (Minimum Spanning Tree) 신장트리 : 모든 정점들은 포함하고 간선은 (정점수-1) 개만 포함하는 트리, 사이클 없음 신장 트리 중에서 간선 가중치의 합이 최소인 신장 트리 ★Kruskal : Union-Find(Disjoint Set) 사용 O(|E|log|V|) Prim : 우선순위큐 사용 O(|E|log|V|) 간선을 기준으로 LinkedList에 담아 정렬 후 Union-Find Union Find by Rank 트리의 높이가 높을 수록 Find Set 수행시간 증가 Union 시 두 집합의 Root 중 Rank 값이 작은 Root를 큰 Root로 변경 Rank 값이 같을 경우에만 랭크 값 증가 public static void unionSet(int a, int b)..
Algorithm
2020. 4. 5. 19:20
반응형
300x250