← 질문 목록
#190깊이 0
그래프 구현 시 인접 행렬과 인접 리스트 중 무엇을 선택하는가?
데이터의 양과 간선의 밀도에 따라 선택한다. 간선이 많다면 인접 행렬을, 적다면 인접 리스트를 쓴다.
| 기준 | 인접 행렬 | 인접 리스트 |
|---|---|---|
| 공간 복잡도 | O(V^2) | O(V+E) |
| 연결 확인 | O(1) | O(degree(V)) |
| 간선 추가/삭제 | 둘 다 O(1) | 추가 O(1), 삭제 O(degree(V)) |
인접 행렬은 2차원 배열로 구현한다. 정점의 수가 적을 때 연결 여부를 즉시 확인하기 좋다. 하지만 정점이 늘수록 메모리 낭비가 심하다.
인접 리스트는 연결된 정점만 저장한다. 희소 그래프에서는 O(V²) 대신 O(V+E)만큼의 공간을 쓴다.
대부분의 그래프가 희소 그래프이므로 인접 리스트를 주로 쓴다. 다만, 모든 정점이 서로 연결된 완전 그래프라면 행렬이 유리하다.