PrimAlgoritm
-
MST 탐색(프림 Prim / 크루스칼 Kruskal)Today_I_Learned/Algorithm 2023. 4. 16. 23:35
1. 일반적인 MST 한 번에 하나의 안전한 간선(Cycle을 발생시키지 않는 간선)을 추가하여 Tree A 를 완성하고 이 때 완성된 Tree A가 MST인지 확인. GENERIC-MST(G, w) A = NULL while A does not form a spanning tree do find an edge (u, v) that is safe for A A = A + (u, v) return A * G 는 Graph 를 의미 2. 프림 알고리즘 개념 현재 선택한 집합 A와 인접하면서, Cut 을 가로지르는 light edge(인접한 Vertex 와의 간선들 중 가중치가 가장 작은 간선)를 선택하여 MST 를 탐색하는 알고리즘. 전제 집합 A는 항상 Tree (Vertex 와 Edge 을 갖는 집합) ..