같은 연결을 다르게 저장하기
정점 A가 B와 C에 이어져 있다면 행렬에서는 A행의 B열과 C열에 연결을 표시할 수 있다. 리스트에서는 A의 이웃 모음에 B와 C를 둔다. 표현 방식이 달라도 원래 나타내려는 연결 관계는 같을 수 있다. 다만 간선의 존재를 찾는 방법과 모든 이웃을 나열하는 방법은 달라진다.
희소한 그래프의 저장량
정점이 10000개면 모든 정점 쌍을 표현하는 표에는 1억 개의 칸이 필요하다. 실제 연결이 적다면 많은 칸이 비어 있을 수 있다. 인접 리스트는 보통 정점과 실제 간선에 비례하는 저장을 사용하지만 이웃 컨테이너와 객체의 부가 비용도 있다. 칸 수와 실제 메모리 바이트를 같은 수치로 취급하지 않는다.
조회하는 질문의 차이
행렬은 정점 번호를 알 때 특정 두 정점의 연결 여부를 직접 확인하기 쉽다. 리스트는 한 정점의 실제 이웃을 차례로 방문하기 자연스럽다. 리스트의 이웃을 배열로 둘지 집합이나 맵으로 둘지에 따라서도 존재 조회 비용이 달라질 수 있다. 인접 리스트라는 큰 분류만으로 모든 연산 비용을 확정하지 않는다.
값의 의미 정하기
가중치를 행렬에 넣을 때 0을 연결 없음의 표시로 사용하면 비용 0인 간선과 혼동할 수 있다. 연결 여부와 가중치의 표현을 명확히 정해야 한다. 방향 그래프에서는 반대쪽 연결이 자동으로 존재하지 않으며 무방향 표현에서는 양쪽 저장이 필요할 수 있다. 중복 간선과 자기 간선의 규칙도 별도로 확인한다.
변환과 알고리즘 비용
저장 표현을 바꾸는 데도 시간과 메모리가 필요하다. 한 번의 계산을 위해 큰 행렬을 새로 만드는 비용이 알고리즘의 이점을 없앨 수 있다. 사용할 연산과 반복 횟수를 기준으로 전체 경로를 비교한다. 작은 그래프를 두 표현으로 만들어 같은 이웃과 가중치를 돌려주는지 확인하면 의미 차이를 검토하기 쉽다.