[Algorithm] Minimum Spanning Tree - Prim
[Algorithm] Minimum Spanning Tree - Kruskals
Spanning Tree Spanning Tree는 어떤 그래프의 정점을 모두 포함한 가장 작은 subgraph를 의미한다. spanning tree를 찾는 가장 쉬운 방법은 DFS와 BFS를 이용하는 것이다. 2023.06.13 - [Computer Science/Data structure & Algo
mobuk.tistory.com
위 글과 이어진 글이다. 먄약 MST가 무엇인지 궁금해서 들어왔다면 위 글을 참고하시길 바란다.
Prim's Algorithm
프림 알고리즘은 한 정점에서 출발한다. 이미 포함된 MST 구조의 노드들에 붙어있는 간선 중 비용이 최소인 간선을 선택하는 것이 핵심이다.
- 한 노드에서 시작한다.
- 그 정점에서 가장 비용이 낮은 간선으로 이동해 그 정점을 MST에 포함시킨다.
- MST에 포함된 모든 정점 중 가장 비용이 낮은 간선을 선택한다.
- 모든 간선을 포함시킬 때가지 3번을 반복한다.
예제 풀이
a에서 시작하겠다.
a에서 갈 수 있는 b, h중 비용이 더 낮은 b를 MST에 포함시킨다. 그 다음은 a,b 와 연결된 간선 중 가장 비용이 낮은 것을 선택한다. 만약 비용이 같으면 아무거나 취하면 된다.
모든 노드가 포함되면 알고리즘은 종료된다.
코드
시간복잡도 : O(Elg(E)) 이다.
만약, 피보나치 힙을 사용한다면 O ( E + V lg(V)) 로 나타낼 수 있다.
https://en.wikipedia.org/wiki/Fibonacci_heap
Fibonacci heap - Wikipedia
From Wikipedia, the free encyclopedia Data structure for priority queue operations Fibonacci heapTypeheapInvented1984Invented byMichael L. Fredman and Robert Endre TarjanAlgorithm Average Worst caseInsert Θ(1) Find-min Θ(1) Delete-min O(log n) Decrea
en.wikipedia.org
'Computer Science > Data structure & Algorithm' 카테고리의 다른 글
| [Algorithm] Union Find (1) | 2023.09.16 |
|---|---|
| [Algorithm] Greedy - Scheduling (0) | 2023.06.13 |
| [Algorithm] Minimum Spanning Tree - Kruskals (0) | 2023.06.13 |
| [Algorithm] Strongly Connected Components (강한 연결 요소) (1) | 2023.06.13 |
| [Algorithm] BFS, DFS (0) | 2023.06.13 |
