6-2. 그래프: 인접 행렬과 인접 리스트

1. 그래프 표현의 두 가지 방법: 인접 행렬과 인접 리스트

그래프는 현실 세계의 다양한 관계를 모델링하는 강력한 도구입니다. 소셜 네트워크의 친구 관계, 지도상의 도시와 도로, 컴퓨터 네트워크의 연결 상태 등, 그래프는 복잡한 시스템을 이해하고 분석하는 데 필수적인 역할을 합니다. 이러한 그래프를 컴퓨터에서 표현하는 방법은 여러 가지가 있으며, 그중 가장 널리 사용되는 두 가지 방법은 인접 행렬 (Adjacency Matrix)과 인접 리스트 (Adjacency List)입니다.

1) 그래프란 무엇인가?

그래프는 정점(Vertex) 또는 노드(Node)라고 불리는 객체들의 집합과, 이들 사이의 관계를 나타내는 간선(Edge)들의 집합으로 구성됩니다. 간선은 정점들을 연결하며, 방향성이 있을 수도 있고(유향 그래프, Directed Graph), 없을 수도 있습니다(무향 그래프, Undirected Graph). 그래프는 복잡한 시스템의 구조를 효과적으로 표현하고, 다양한 알고리즘을 통해 문제를 해결하는 데 사용됩니다.

2) 인접 행렬과 인접 리스트의 필요성

그래프를 컴퓨터에 저장하고 조작하려면, 그래프의 구조를 효과적으로 표현하는 데이터 구조가 필요합니다. 인접 행렬과 인접 리스트는 이러한 목적을 달성하기 위한 두 가지 주요 방법입니다. 각각은 그래프의 구조를 저장하는 방식, 메모리 사용량, 그리고 그래프 연산의 속도에서 차이를 보이며, 문제의 특성에 따라 적합한 방법을 선택하는 것이 중요합니다.

2. 인접 행렬: 행렬을 이용한 그래프 표현

인접 행렬은 2차원 배열(행렬)을 사용하여 그래프를 표현하는 방법입니다. 정점의 개수가 $n$개인 그래프의 경우, $n \times n$ 크기의 배열을 사용합니다. 배열의 각 요소 matrix[i][j]는 정점 $i$에서 정점 $j$로 가는 간선이 존재하는지를 나타냅니다.

1) 구현 방식

• 무향 그래프: matrix[i][j]와 matrix[j][i]는 동일한 값을 가집니다. 간선이 존재하면 1, 존재하지 않으면 0으로 표시합니다.
• 유향 그래프: matrix[i][j]는 정점 $i$에서 정점 $j$로 가는 간선의 존재 여부를 나타냅니다. 간선이 존재하면 1, 존재하지 않으면 0으로 표시합니다.
• 가중치 그래프: 간선의 가중치를 저장합니다. 간선이 존재하지 않으면 무한대(∞) 또는 특정 값을 사용하여 표현합니다.

2) 장점

• 간단한 구현: 구현이 쉽고 직관적입니다.
• 빠른 간선 존재 여부 확인: 특정 두 정점 사이의 간선 존재 여부를 $O(1)$ 시간에 확인할 수 있습니다.
• 직관적인 표현: 그래프의 구조를 시각적으로 쉽게 파악할 수 있습니다.

3) 단점

• 메모리 사용량: 정점의 개수가 많아질수록 $O(n^2)$의 메모리를 사용하므로, 메모리 사용량이 많습니다. 밀집 그래프(간선이 많은 그래프)에는 적합하지만, 희소 그래프(간선이 적은 그래프)에는 메모리 낭비가 발생합니다.
• 모든 간선을 순회하는 경우 비효율적: 모든 간선을 순회하려면 $O(n^2)$의 시간이 소요됩니다.

4) 예시

5개의 정점을 가진 무향 그래프를 인접 행렬로 표현하면 다음과 같습니다.

위 그림에서, matrix[0][1]과 matrix[1][0]은 모두 1의 값을 가지는데, 이는 정점 A와 B 사이에 간선이 존재함을 의미합니다. matrix[0][3]은 0의 값을 가지므로, 정점 A와 D 사이에는 간선이 없습니다.

3. 인접 리스트: 연결 리스트를 이용한 그래프 표현

인접 리스트는 각 정점에 연결된 정점들의 목록을 연결 리스트 형태로 저장하여 그래프를 표현하는 방법입니다. 각 정점은 해당 정점과 인접한 정점들의 목록을 가집니다.

1) 구현 방식

• 각 정점에 해당하는 리스트를 생성합니다.
• 각 리스트에는 해당 정점과 연결된 다른 정점들을 저장합니다.
• 무향 그래프: 정점 $i$와 $j$ 사이에 간선이 존재하면, 정점 $i$의 리스트와 정점 $j$의 리스트에 각각 $j$와 $i$를 추가합니다.
• 유향 그래프: 정점 $i$에서 $j$로 가는 간선이 존재하면, 정점 $i$의 리스트에 $j$를 추가합니다.
• 가중치 그래프: 각 리스트의 요소에 연결된 정점과 함께 가중치를 저장합니다.

2) 장점

• 메모리 효율성: 간선의 개수만큼의 메모리를 사용하므로, 희소 그래프에 적합합니다. 메모리 사용량은 $O(V + E)$이며, 여기서 $V$는 정점의 수, $E$는 간선의 수입니다.
• 특정 정점의 인접 정점 찾기 용이: 특정 정점에 연결된 모든 정점을 빠르게 찾을 수 있습니다.
• 간선의 추가/삭제 용이: 연결 리스트의 특성상 간선의 추가 및 삭제가 용이합니다.

3) 단점

• 간선 존재 여부 확인 속도: 특정 두 정점 사이의 간선 존재 여부를 확인하는 데 $O(V)$의 시간이 소요될 수 있습니다. (최악의 경우).
• 구현 복잡도: 인접 행렬보다 구현이 조금 더 복잡합니다.

4) 예시

5개의 정점을 가진 무향 그래프를 인접 리스트로 표현하면 다음과 같습니다.

위 그림에서, 정점 A의 리스트는 [B, D]를 포함합니다. 이는 정점 A가 정점 B와 D에 연결되어 있음을 의미합니다.

4. 인접 행렬과 인접 리스트 비교

여기서 $V$는 정점의 수, $E$는 간선의 수를 나타냅니다. degree(v)는 정점 v에 연결된 간선의 수를 의미합니다.

5. 메모리 사용량과 접근 속도 분석

1) 메모리 사용량

인접 행렬은 정점의 수의 제곱에 비례하는 메모리를 사용합니다. 따라서 정점의 수가 증가하면 메모리 사용량이 급격하게 증가합니다. 인접 리스트는 정점의 수와 간선의 수의 합에 비례하는 메모리를 사용합니다. 희소 그래프의 경우, 간선의 수가 적기 때문에 인접 리스트가 메모리 효율성 측면에서 유리합니다.

2) 접근 속도

인접 행렬은 특정 두 정점 사이의 간선 존재 여부를 $O(1)$ 시간에 확인할 수 있습니다. 인접 리스트는 최악의 경우 $O(V)$의 시간이 소요되지만, 특정 정점에 연결된 모든 정점을 찾는 것은 $O(degree(v))$ 시간에 가능합니다. 즉, 특정 정점의 연결 정보에 빠르게 접근해야 하는 경우에는 인접 리스트가 더 효율적일 수 있습니다.

6. 실제 사용 사례 및 선택 가이드

1) 인접 행렬의 활용

• 소규모 그래프: 정점의 수가 적은 그래프를 다룰 때 간단하게 구현하고 성능 저하가 크지 않아 유용합니다.
• 간선 존재 여부 빈번한 확인: 특정 두 정점 사이의 연결 관계를 자주 확인해야 하는 경우 (예: 게임 맵에서 두 지점 간의 연결 상태 확인).
• 그래프 밀집도 분석: 그래프의 밀집도를 빠르게 파악해야 하는 경우.

2) 인접 리스트의 활용

• 대규모 희소 그래프: 소셜 네트워크, 웹 페이지 링크 구조 등, 대규모 그래프를 다루면서 간선의 수가 적은 경우에 적합합니다.
• 특정 정점의 인접 정점 정보 활용: 특정 정점과 연결된 모든 정점을 빠르게 찾아야 하는 경우 (예: 친구 추천 기능, 최단 경로 탐색 알고리즘).
• 그래프 탐색 알고리즘 (DFS, BFS): 그래프 탐색 알고리즘을 구현할 때 인접 리스트가 효율적입니다.

3) 선택 가이드

• 그래프 크기: 그래프의 크기가 작고 간선의 수가 많다면 인접 행렬을, 그래프가 크고 간선의 수가 적다면 인접 리스트를 선택하는 것이 좋습니다.
• 연산 빈도: 간선 존재 여부 확인이 빈번하다면 인접 행렬을, 특정 정점에 연결된 정점들을 찾는 연산이 빈번하다면 인접 리스트를 선택하는 것이 좋습니다.
• 메모리 제약: 메모리가 제한적이라면 인접 리스트를 선택하는 것이 좋습니다.

7. 결론

인접 행렬과 인접 리스트는 그래프를 표현하는 데 사용되는 두 가지 기본적인 데이터 구조입니다. 각 구조는 고유한 장단점을 가지며, 문제의 특성에 따라 적합한 방법을 선택하는 것이 중요합니다. 인접 행렬은 간단한 구현과 빠른 간선 존재 확인을 제공하지만, 메모리 사용량이 많다는 단점이 있습니다. 인접 리스트는 메모리 효율성이 뛰어나고 특정 정점의 인접 정점 정보를 빠르게 찾을 수 있지만, 간선 존재 여부를 확인하는 데는 더 많은 시간이 소요될 수 있습니다. 문제의 요구 사항, 그래프의 크기, 메모리 제약 등을 고려하여 적절한 방법을 선택하면, 그래프 관련 문제를 효과적으로 해결할 수 있습니다.