prim's algorithm (1) 썸네일형 리스트형 127. Prim's Algorithm 프림 알고리즘(Prim's Algorithm)은 무향 그래프의 최소 스패닝 트리를 구하는 두 번째 알고리즘으로, 다음과 같은 방법으로 작동한다. 1. 그래프에서 정점 하나를 임의로 골라서 $v$라고 한다. 2. 연결하는 한쪽 정점이 $v$와 연결된 정점들의 집합에 포함되고 다른 정점은 집합에 포함되지 않는 간선들 중 가중치가 가장 작은 간선 하나를 선택하고 최소 스패닝 트리에 추가한다. 3. 모든 정점이 $v$와 연결될 때까지 2번 과정을 반복한다. 이것도 설명이 짧아서 예시를 같이 살펴보면 편할 것이다. 앞에서 나온 그래프에서 정점 $\text{H}$가 $v$로 선택되었다면 다음과 같이 스패닝 트리가 만들어지게 된다. 먼저 정점 $\text{H}$와 연결된 간선 중 가중치가 가장 작은 간선이 최소 스패.. 이전 1 다음
