Spanning Tree
- 신장 트리
- 신장 트리가 되기 위한 조건
- 그래프 내의 모든 정점을 포함하고 있어야 함.
- 무방향 연결 그래프
- 싸이클을 제거한 부분 그래프
- 트리가 되기 위한 최소한의 간선만 남긴것
DFS Spanning Tree
BFS Spanning Tree
MST (Minimum Spanning Tree)
- 최소 신장 트리 - 비용이 최소인 신장 트리
- MST의 비용 - 신장 트리를 구성하는 간선 가중치의 합
- MST가 되기 위한 조건
- 가중 무방향 그래프
- 이외의 조건은 모두 신장 트리와 동일
- MST를 구하는 2가지 알고리즘 - Kruskal, Prim
Kruskal Algorithm
- 임의의 정점에서 시작, 가장 작은 가중치의 간선들을 총 n-1개 선택 (n : number of vertex)
- 이때, 싸이클이 연결되지 않도록 선택하는 예외처리가 필요함.
- 항상 Optimal Solution이 도출됨.
Prim Algorithm
- 임의의 정점을 시작으로 임의의 정점에 연결된 간선들중 가장 작은 가중치의 간선부터 순서대로 n-1개의 간선을 선택
- 이떄, 싸이클이 연결되지 않도록 선택하는 예외처리가 필요함.
- 각 단계에서 최선의 답을 선택하는 과정 반복 -> 최종 해에 도달
- 최선의 가중치 (가장 작은 가중치)는 minHeap을 통해서 구현하고 확인 가능
- 항상 Optimal Solution이 도출됨.
Time Complexity of Kruskal, Prim Algorithm
- V - number of Vertex / E - number of Edge
- Kruskal : O( E log E)
- Prim : O( E + V log V) -> O( E log V)
- 그래프 표현을 인접 행렬 또는 인접 리스트를 이용할 경우, 달라질 수 있음
- 그래프 간선의 수가 상대적으로 적고 많음에 따라서 시간 복잡도의 크기가 달라질 수 있음
-> 간선의 수가 많으면 Prim이 효과적 ( 이유: 간선이 많을 경우, log V < log E 이기 떄문에)
'Python > 자료구조, 알고리즘' 카테고리의 다른 글
| 자료구조, 알고리즘) Graph - About Graph, DFS, BFS (1) | 2024.05.22 |
|---|---|
| 자료구조, 알고리즘) Sorting - Shellsort, Mergesort, Heapsort, Radixsort (1) | 2024.05.17 |
| 자료구조, 알고리즘) Sorting - Bubblesort, Selectionsort, Insertionsort, Quicksort + Partition (1) | 2023.12.10 |
| 자료구조) Binary Search Tree (6) | 2023.12.05 |
| 자료구조) Binary Tree (4) | 2023.11.28 |