인접 리스트(Adjacency List)는 그래프를 표현하는 방법 중 하나로, 각 정점이 연결된 이웃 정점들을 리스트 형태로 저장하는 방식이다. 이 방법은 간선이 적은 희소 그래프(Sparse Graph)에 적합하며, 메모리 효율성이 높다.
정의
인접 리스트는 그래프 G = (V, E)에 대해 다음과 같이 정의된다.
- 각 정점 Vi는 자신과 연결된 정점들의 리스트를 갖는다.
- 간선이 존재하면 해당 정점을 리스트에 포함한다.
인접 리스트의 특징
- 그래프의 정점 개수가 V, 간선 개수가 E일 때, 인접 리스트의 공간 복잡도는 O(V + E)이다.
- 간선이 많은 밀집 그래프(Dense Graph)보다는 희소 그래프에 적합하다.
- 간선이 존재하는지 확인하는 연산은 O(degree) 시간이 소요된다.
- 특정 정점의 모든 인접 정점을 찾는 것이 빠르다.
인접 리스트 예제
다음 무향 그래프를 인접 리스트로 표현한다.
- 정점 집합 V = {1, 2, 3, 4}
- 간선 집합 E = {(1,2), (1,3), (2,3), (3,4)}
| 정점 | 인접 리스트 |
|---|---|
| 1 | 2 → 3 |
| 2 | 1 → 3 |
| 3 | 1 → 2 → 4 |
| 4 | 3 |
가중 그래프의 인접 리스트
가중 그래프(Weighted Graph)의 경우, 인접 리스트에는 연결된 정점뿐만 아니라 가중치도 포함된다.
| 정점 | 인접 리스트 (정점, 가중치) |
|---|---|
| 1 | (2, 5) → (3, 2) |
| 2 | (1, 5) → (3, 1) |
| 3 | (1, 2) → (2, 1) → (4, 3) |
| 4 | (3, 3) |
인접 리스트 vs 인접 행렬
| 항목 | 인접 리스트 | 인접 행렬 |
|---|---|---|
| 공간 복잡도 | O(V + E) | O(V²) |
| 간선 존재 확인 | O(degree) | O(1) |
| 모든 간선 순회 | O(E) | O(V²) |
| 희소 그래프 적합성 | 높음 | 낮음 |
인접 리스트의 활용
- 그래프 탐색
- 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)에 적합함.
- 최단 경로 알고리즘
- 다익스트라 알고리즘, 벨만-포드 알고리즘에서 활용됨.
- 네트워크 분석
- 컴퓨터 네트워크, 소셜 네트워크 분석(SNA)에 사용됨.
같이 보기
참고 문헌
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
- Wikipedia - Adjacency List