그래프는 다양한 기준에 따라 분류할 수 있습니다. 간선에 방향이 있는지에 따라 유향 그래프(directed graph)와 무향 그래프(undirected graph)로 나뉘고, 간선에 가중치가 부여되어 있는지에 따라 가중 그래프(weighted graph)와 비가중 그래프(unweighted graph)로 구분됩니다. 이번 글에서는 가중 그래프를 메모리에 표현하는 대표적인 두 가지 방법을 예시와 함께 살펴보겠습니다.
설명을 위해 다음과 같은 예시 그래프를 사용하겠습니다.
인접 행렬(Adjacency Matrix) 표현
가중 그래프를 인접 행렬 형태로 저장할 때는 이 행렬을 비용 행렬(cost matrix)이라고 부릅니다. 행렬의 각 셀 M[i, j]에는 노드 i에서 노드 j로 향하는 간선의 가중치가 저장됩니다. 두 노드 사이에 간선이 존재하지 않으면 무한대(∞)를 기입하고, 자기 자신을 가리키는 경우에는 0을 넣습니다.
| 0 | ∞ | 6 | 3 | ∞ |
| 3 | 0 | ∞ | ∞ | ∞ |
| ∞ | ∞ | 0 | 2 | ∞ |
| ∞ | 1 | 1 | 0 | ∞ |
| ∞ | 4 | ∞ | 2 | 0 |
예를 들어 위 행렬에서 M[0, 2]의 값이 6이라면, 0번 노드에서 2번 노드로 가는 간선의 가중치가 6임을 의미합니다. 반면 M[0, 1]이 ∞이므로 0번 노드에서 1번 노드로 직접 연결된 간선은 없습니다.
인접 리스트(Adjacency List) 표현
인접 리스트 방식에서는 각 노드마다 연결된 간선 정보를 리스트로 관리합니다. 리스트의 각 요소는 두 개의 값을 가지는데, 첫 번째 값은 도착 노드(destination node)이고, 두 번째 값은 해당 간선의 가중치(weight)입니다. 표현 방식은 아래와 같습니다.
두 표현 방식의 비교
인접 행렬은 두 노드 간의 연결 여부와 가중치를 O(1) 시간에 즉시 확인할 수 있다는 장점이 있지만, 항상 O(V²) 크기의 공간을 차지합니다. 반면 인접 리스트는 실제 존재하는 간선만 저장하므로 O(V + E) 공간으로 효율적이며, 특히 간선 수가 적은 희소 그래프(sparse graph)에서 유리합니다. 따라서 그래프의 밀도와 수행해야 할 연산의 종류에 따라 적절한 표현 방식을 선택하는 것이 중요합니다.