정점 수가 작고 그래프가 조밀합니다. O(V²) Prim이 힙 기반 구현보다 유리할 수 있는 이유는 무엇인가요?

꼬리 질문을 독립 문항으로 확장했습니다. 원래 문항에서 맥락 보기 →

잠깐, 답변을 보기 전에
먼저 내 말로 설명해 볼까요?

답변과 점검 포인트 펼치기답변 접기

구두 답변

정의를 외우기보다, 원리와 조건을 연결해 설명해 보세요.

조밀 그래프는 E가 V²에 가까워 힙 관리·간선 저장 비용이 클 수 있습니다. 배열로 미방문 최솟값을 O(V)에 선택하고 행렬을 순회하는 O(V²) Prim이 작은 V에서 단순하고 locality가 좋을 수 있습니다.

같은 그래프에서 메모리·상수 비용을 비교합니다. 희소 그래프에는 다른 선택이 유리할 수 있습니다. 동점·비연결·음수 간선에서도 MST 목적과 결과 불변식을 유지합니다.

이해가 드러나는 지점을 확인해 보세요.

조밀 그래프는 E가 V²에 가까워 힙 관리·간선 저장 비용이 클 수 있습니다. 배열로 미방문 최솟값을 O(V)에 선택하고 행렬을 순회하는 O(V²) Prim이 작은 V에서 단순하고 locality가 좋을 수 있습니다.
동점·비연결·음수 간선에서도 MST 목적과 결과 불변식을 유지합니다.

놓치기 쉬운 조건과 오해를 짚어 보세요.

하나 더 질문하며 이해의 범위를 넓혀 보세요.

득점·감점 포인트는 학습용 자기 점검 기준이며, 특정 회사의 실제 채점표가 아닙니다.

답변을 보충하는 개념·예제·슈도코드를 읽어 보세요.