목록prim (1)

유블로그

[알고리즘] Prim 알고리즘

- 간선 수가 많을 때 kruskal 알고리즘은 불리하다. - 간선 개수에 비해 정점의 개수가 적은 경우 정점 중심인 Prim이 유리할 수 있다. (불리한 경우도 있음) - 간적쿠 간만프 ! (간선적으면크루스칼, 간선많으면프림) - Prim : 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어가는 방식 - 과정 1. 임의 정점을 하나 선택해서 시작 2. 선택한 정점과 인접한 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택 3. 모든 정점이 선택될 때까지 1, 2 를 반복 + MST만들기 위해 선택된 정점과 선택되지 않은 정점들 정보를 유지 public class PrimTest { public static void main(String[] args) throws Exception..
알고리즘 2020. 8. 31. 16:01
이전 Prev 1 Next 다음