-
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 을 갖는 집합)
추가 지식
Cut구현 팁
Set 을 사용
Algorithm : 아직 이해 100% 안 됨…. π[v]?
MST-PRIM(G, w, r) // r = root (시작 정점) for u in V[G] key[u] = ∞ // 현재 위치에서 나머지 정점(Vertex)들로의 가중치 π[u] = NULL // 현재 정점의 다음 정점(?) key[r] = 0 Q = V[G] while Q != NULL u = EXTRACT-MIN(Q) // Light Edge로 연결된 정점 선택 for v in Adj[u] if v in Q and w(u, v) < key[v] π[v] = u key[v] = w(u, v)
3. 크루스칼 Kruskal 알고리즘
'Today_I_Learned > Algorithm' 카테고리의 다른 글
99클럽 코테 스터디 5일차 TIL: 배열, Leetcode 1476. Subrectangle Queries (0) 2024.06.15 99클럽 코테 스터디 4일차 TIL : Graph, 프로그래머스, 순위 (0) 2024.06.13 99클럽 코테 스터디 3일차 TIL: Graph, Dijkstra, 프로그래머스, 가장 먼 노드 (0) 2024.06.12 99클럽 코테 스터디 1일차 : 그리디, 구명보트(프로그래머스) (0) 2024.06.06 탐욕 Greedy Algorithm (0) 2023.04.16