[Data Structure] 최소 신장 트리 - Prim MST Algorithm

Prim MST Algorithm - 시작 정점에서부터 신장 트리 집합을 확장해가는 알고리즘 - 인접 정점들 중에서 가중치가 최소인 정점을 선택해가면서 트리를 확장 이전 단계에서 만들어진 신장 트리를 확장 - n개의 정점에 대해서 n-1개의 간선을 선택하면 알고리즘 종료 - 배열로 구현 or 최소히프로 구현 - 어떤 정점에서 시작하던간에 똑같은 트리 생성 - O(n²) ※ 각 정점으로부터 거리 distance 배열, 선택된 정점 selected 배열 (모든 정점 distance = INF로 초기화) v의 인접 정점들 distance 업데이트 인접 정점들 중 distance가 가장 낮은 정점(w) 선택 v와 w를 하나의 그룹으로 간주하고 해당 그룹으로부터 distance 다시 업데이트 n-1개 간선 선택할..

2021.12.25