티스토리 뷰
728x90
반응형
최소신장트리 (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) { int rootA = findSet(a); int rootB = findSet(b); if(rootA != rootB) { if(R[rootA] > R[rootB]) { P[rootB] = rootA; } else { P[rootA] = rootB; if(R[rootA] == R[rootB]) R[rootB]++; } } } public static int findSet(int n) { if(n != P[n]) P[n] = findSet(P[n]); return P[n]; }
728x90
반응형
'Algorithm' 카테고리의 다른 글
최단 경로 알고리즘 - Floyd Warshall (0) | 2020.04.05 |
---|---|
최단 경로 알고리즘 - Bellman Ford (0) | 2020.04.05 |
최단 경로 알고리즘 - 다익스트라 (Dijkstra) (0) | 2020.04.05 |
너비 우선 탐색 Breadth First Search (BFS) (0) | 2020.04.05 |
깊이 우선 탐색 Depth First Search (DFS) (0) | 2020.04.05 |
반응형
300x250