위키득계정 ↗
기술

인접 행렬과 인접 리스트

인접 행렬과 인접 리스트기술
인접 행렬
정점 쌍별 표 형태
인접 리스트
정점별 이웃 모음
선택 기준
정점 수와 간선 수 및 조회 패턴
추가 구분
방향과 가중치 및 중복 간선
인접 행렬은 정점 쌍의 연결 정보를 표로 저장하고 인접 리스트는 정점별 이웃을 모아 저장한다. 그래프의 밀도와 자주 수행할 조회에 따라 저장량과 연산 비용의 균형이 달라진다.

같은 연결을 다르게 저장하기

정점 A가 B와 C에 이어져 있다면 행렬에서는 A행의 B열과 C열에 연결을 표시할 수 있다. 리스트에서는 A의 이웃 모음에 B와 C를 둔다. 표현 방식이 달라도 원래 나타내려는 연결 관계는 같을 수 있다. 다만 간선의 존재를 찾는 방법과 모든 이웃을 나열하는 방법은 달라진다.

희소한 그래프의 저장량

정점이 10000개면 모든 정점 쌍을 표현하는 표에는 1억 개의 칸이 필요하다. 실제 연결이 적다면 많은 칸이 비어 있을 수 있다. 인접 리스트는 보통 정점과 실제 간선에 비례하는 저장을 사용하지만 이웃 컨테이너와 객체의 부가 비용도 있다. 칸 수와 실제 메모리 바이트를 같은 수치로 취급하지 않는다.

조회하는 질문의 차이

행렬은 정점 번호를 알 때 특정 두 정점의 연결 여부를 직접 확인하기 쉽다. 리스트는 한 정점의 실제 이웃을 차례로 방문하기 자연스럽다. 리스트의 이웃을 배열로 둘지 집합이나 맵으로 둘지에 따라서도 존재 조회 비용이 달라질 수 있다. 인접 리스트라는 큰 분류만으로 모든 연산 비용을 확정하지 않는다.

값의 의미 정하기

가중치를 행렬에 넣을 때 0을 연결 없음의 표시로 사용하면 비용 0인 간선과 혼동할 수 있다. 연결 여부와 가중치의 표현을 명확히 정해야 한다. 방향 그래프에서는 반대쪽 연결이 자동으로 존재하지 않으며 무방향 표현에서는 양쪽 저장이 필요할 수 있다. 중복 간선과 자기 간선의 규칙도 별도로 확인한다.

변환과 알고리즘 비용

저장 표현을 바꾸는 데도 시간과 메모리가 필요하다. 한 번의 계산을 위해 큰 행렬을 새로 만드는 비용이 알고리즘의 이점을 없앨 수 있다. 사용할 연산과 반복 횟수를 기준으로 전체 경로를 비교한다. 작은 그래프를 두 표현으로 만들어 같은 이웃과 가중치를 돌려주는지 확인하면 의미 차이를 검토하기 쉽다.

관련 문서

알고리즘 / 배열 / 너비 우선 탐색 / 깊이 우선 탐색