프림 알고리즘(Prim’s Algorithm)

date

May 7, 2023

slug

mst-prim

author

status

Public

category

💡 Algorithm

tags

MST(최소 스패닝 트리)

그래프

summary

간선이 많으면 프림, 항상 가장 가까운 정점으로

type

Post

thumbnail

필요한 사전 지식

Prim’s Algorithm 프림 알고리즘

알고리즘 과정

1. 임의의 정점 V을 비어있는 트리 T에 포함시킨다

2. T에 있는 노드와 T에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다
1. 이때 사이클을 막기 위해, 연결된 정점이 이미 트리에 있다면 그 다음 순서의 간선을 찾는다

3. 찾은 간선이 연결하는 두 개의 노드 중 T에 없던 노드와 그 간선을 T에 포함시킨다

4. 모든 노드가 T에 포함될 때까지 = (n-1)개의 간선을 가질 때까지 2~3 반복

자료구조 2가지에 따른 시간복잡도

1. 힙(Min heap) : 시간복잡도 O(E logV)
• 탐색 O(V logV)
• 모든 노드에 대해 탐색을 진행 → O(V)
• 우선순위 큐를 사용하여 매 노드마다 최소 간선을 찾음 → O(logV)
• 우선순위 큐 구성 O(E logV)
• 각 노드의 인접 간선 찾기 = 모든 노드의 차수와 같음 → O(2E) = O(E)
• 각 간선을 힙에 넣기 → O(logV)
• 합계 : O(V logV + E logV) = O(E logV)

2. 배열 : 시간복잡도 O(V*V)
1. 각 정점에 최소 간선을 갖는 정점 탐색을 매 정점마다 수행 → O(V*V)
2. 탐색 결과를 기반으로 각 정점의 최소 비용 연결 정점 탐색 → O(1)

Simulation

1. 임의의 정점 A에서 시작

2. A와 인접한 노드 B, C 중 C가 가장 가중치가 낮은 간선으로 연결되어 있으니 C를 집합에 넣고 비용에 AC 가중치를 더함

1. A, C와 인접한 노드들 중 가장 낮은 가중치의 간선으로 연결된 정점 B를 집합에 넣고 비용에 BC 가중치를 더함

1. A, C, B와 인접한 노드들 중 가장 낮은 가중치로 연결된 정점은 D이므로 집합에 D를 넣고 CD 가중치를 더함

1. A, C, B, D와 인접한 노드들 중 가장 낮은 가중치로 연결된 정점은 E이므로 집합에 E를 넣고 DE 가중치를 더함

1. A, C, B, D, E와 인접한 노드들 중 가장 낮은 가중치로 연결된 정점 F를 집합에 넣고 DF 가중치를 더함. 트리의 집합에 속한 원소의 개수가 N이 되었으므로 탐색을 중단. 탐색 결과 최소 신장 트리 구축의 비용은 13으로 종료

Kruskal ↔ Prim

• 간선이 많을 땐 프림, 간선이 없을 땐 크루스칼

• Sparse Graph는 크루스칼 알고리즘이 유리

• Dense Graph는 프림 알고리즘이 유리