그래프 표현은 취향이 아니라 입력 규모와 “무엇을 자주 묻는가”로 고른다.
| 판정 축 | 인접 리스트가 맞는 신호 | 인접 행렬이 맞는 신호 | 실패 신호 |
|---|---|---|---|
| 밀도 | E가 V보다 훨씬 작음 | E가 V²에 가까움 | 희소 그래프를 행렬로 만들어 메모리 폭증 |
| 간선 존재 질의 | 이웃 순회가 더 많음 | hasEdge(u, v)가 매우 많음 | 리스트에서 매번 이웃 전체 탐색 |
| 간선 속성 | 가중치, 라벨, 시간 등 edge 객체 필요 | 속성이 거의 없고 boolean이면 충분 | 행렬 셀에 복잡한 구조를 억지 저장 |
| 업데이트 | 간선 삽입/삭제가 잦음 | 정점 수가 작고 고정 | 삭제 비용을 고려하지 않음 |