인접 행렬(Adjacency Matrix)은 그래프를 표현하는 방법 중 하나로, 정점 간의 연결 관계를 2차원 행렬 형태로 나타낸다. 인접 행렬은 그래프의 저장과 연산을 효율적으로 수행하는 데 사용된다.
정의
인접 행렬 A는 그래프 G = (V, E)에 대해 다음과 같이 정의된다.
- Aij = 1 (i에서 j로 간선이 존재하면 1)
- Aij = 0 (i에서 j로 간선이 없으면 0)
무향 그래프의 경우 인접 행렬은 대칭 행렬이 된다.
인접 행렬의 특징
- 그래프의 정점 개수가 V일 때, 인접 행렬의 크기는 V × V이다.
- 밀도가 높은 그래프(간선이 많은 경우)에 적합하다.
- 간선이 있는지 확인하는 연산은 O(1)로 빠르다.
- 공간 복잡도는 O(V²)이며, 희소 그래프에는 비효율적이다.
인접 행렬 예제
다음 무향 그래프를 인접 행렬로 표현한다.
- 정점 집합 V = {1, 2, 3, 4}
- 간선 집합 E = {(1,2), (1,3), (2,3), (3,4)}
| 정점 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 0 |
| 2 | 1 | 0 | 1 | 0 |
| 3 | 1 | 1 | 0 | 1 |
| 4 | 0 | 0 | 1 | 0 |
가중 그래프의 인접 행렬
가중 그래프(Weighted Graph)의 경우, 인접 행렬의 값은 간선의 가중치로 저장된다.
- Aij = w (i에서 j로 가중치 w의 간선이 있을 경우)
- Aij = 0 (간선이 없을 경우)
예제:
| 정점 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 0 | 5 | 2 | 0 |
| 2 | 5 | 0 | 1 | 0 |
| 3 | 2 | 1 | 0 | 3 |
| 4 | 0 | 0 | 3 | 0 |
인접 행렬 vs 인접 리스트
| 항목 | 인접 행렬 | 인접 리스트 |
|---|---|---|
| 공간 복잡도 | O(V²) | O(V + E) |
| 간선 존재 확인 | O(1) | O(degree) |
| 모든 간선 순회 | O(V²) | O(E) |
| 희소 그래프 적합성 | 낮음 | 높음 |
인접 행렬의 활용
- 그래프 탐색
- DFS, BFS 알고리즘에서 간선 존재 여부 확인이 빠름.
- 최단 경로 알고리즘
- 플로이드-워셜 알고리즘에서 인접 행렬을 사용함.
- 네트워크 분석
- 컴퓨터 네트워크 및 사회 연결망 분석(SNA)에 활용됨.
같이 보기
참고 문헌
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.