← 질문 목록
#138깊이 0
그래프를 인접 행렬과 인접 리스트 중 어떤 방식으로 구현해야 하는가?
답변 연습
내 답변 적어보기접힘
이 브라우저에 자동 저장 · 0자
모범답안 확인하기내 답변 뒤에 열어보세요
간선의 밀도와 탐색 연산의 주된 목적에 따라 결정한다. 간선이 많은 밀집 그래프는 인접 행렬을, 간선이 적은 희소 그래프는 인접 리스트를 선택하는 것이 유리하다.
| 기준 | 인접 행렬 | 인접 리스트 |
|---|---|---|
| 공간 복잡도 | O(V²) | O(V + E) |
| 간선 존재 확인 | O(1) | O(degree(V)) |
| 인접 정점 탐색 | O(V) | O(degree(V)) |
인접 행렬은 2차원 배열을 써서 두 정점 간의 연결 여부를 상수 시간에 확인한다. 정점 수가 많고 간선이 적다면 메모리 낭비가 크다.
인접 리스트는 각 정점에 연결된 정점만 가변 배열이나 연결 리스트로 저장한다. 메모리를 절약하지만 특정 두 정점이 연결되었는지 확인하려면 리스트를 순회해야 한다.
실무나 일반적인 문제 해결에서는 정점 수에 비해 간선 수가 적은 희소 그래프가 많아 인접 리스트를 주로 사용한다.