그래프를 인접 행렬과 인접 리스트 중 어떤 방식으로 구현해야 하는가?

간선의 밀도와 탐색 연산의 주된 목적에 따라 결정한다. 간선이 많은 밀집 그래프는 인접 행렬을, 간선이 적은 희소 그래프는 인접 리스트를 선택하는 것이 유리하다.

인접 행렬은 2차원 배열을 써서 두 정점 간의 연결 여부를 상수 시간에 확인한다. 정점 수가 많고 간선이 적다면 메모리 낭비가 크다.

인접 리스트는 각 정점에 연결된 정점만 가변 배열이나 연결 리스트로 저장한다. 메모리를 절약하지만 특정 두 정점이 연결되었는지 확인하려면 리스트를 순회해야 한다.

실무나 일반적인 문제 해결에서는 정점 수에 비해 간선 수가 적은 희소 그래프가 많아 인접 리스트를 주로 사용한다.