prim's algorithm
-
Prim's Algorithm대학/알고리즘 2023. 6. 9. 21:32
Minimum Spanning Tree Greedy 알고리즘의 예시인 Prim's Algorithm을 살펴보기 전에 그 알고리즘이 다루는 Minimum Spanning Tree의 정의부터 알아보자. - Tree Graph 구조에서 cycle 구조가 존재하지 않고, 연결되지 않은 vertex가 없고, edge에 방향성이 없는 그래프. - Spanning Tree 오리지널 Tree의 부분 트리. 즉, 오리지널 Tree에서 일부 edge가 없는 트리를 의미한다. - Minimum Spanning Tree Spanning Tree 중, edge의 weight의 합이 최소가 되는 트리. G1이 오리지널 트리라 했을 때, G4, G5만이 G1의 Minimum Spanning Tree이다. G2의 경우에는 G1에 S..