Prim VS Dijkstra - 전체적인 틀은 BFS와 유사 Prim 각 정점의 distance는 집합 S에 존재하는 정점과 연결하는데 발생하는 weight → 각 정점의 weight는 여러 번 바뀐다 → 시작 정점 v ~ 모든 정점에 도달하는 최소비용 계산 Dijkstra 시작 정점 v ~ 모든 정점까지의 최단 거리 계산 Prim : 집합 S에서 해당 정점까지의 거리 (S ~ v) DIjkstra : 집합 S의 시작정점 r에서 해당 정점까지의 가장 짧은 거리 (S(r) ~ v) 알고리즘 비교 Prim void prim_mst(graph* g, int v) { // v = 시작 정점 init_distance(distance); init_selected(selected); distance[v] = 0; ..

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