graph를 어떻게 표현하나요: adjacency list 대 adjacency matrix?

Question

Accepted Answer

**graph(그래프)**는 **간선(edge)**으로 연결된 **정점(vertex)**들의 집합입니다. 두 가지 표준 표현은 **adjacency list(인접 리스트)**(각 정점이 이웃을 저장)와 **adjacency matrix(인접 행렬)**(V×V 불리언 격자)입니다. 선택은 그래프의 **밀도(density)**에 따라 달라집니다.

## 두 가지 형태

```text
Graph:  0 - 1
        |   |
        2 - 3

Adjacency list:          Adjacency matrix:
0: [1, 2]                    0 1 2 3
1: [0, 3]                 0 [0 1 1 0]
2: [0, 3]                 1 [1 0 0 1]
3: [1, 2]                 2 [1 0 0 1]
                          3 [0 1 1 0]
```

## 코드

```python
# Adjacency list (리스트의 dict) — 희소 그래프에 선호됨
adj = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}
neighbors = adj[1]            # 정점의 이웃을 얻는 데 O(1)

# Adjacency matrix
matrix = [[0]*4 for _ in range(4)]
matrix[0][1] = matrix[1][0] = 1
has_edge = matrix[0][1] == 1  # O(1) 간선 조회
```

## 비교 (정점 V개, 간선 E개)

| | Adjacency list | Adjacency matrix |
|---|---|---|
| 공간 | O(V + E) | O(V²) |
| 간선 존재? | O(degree) | O(1) |
| 이웃 순회 | O(degree) | O(V) |
| 적합한 경우 | 희소 그래프 | 밀집 그래프 |

## 왜 중요한가

대부분의 실제 그래프(소셜 네트워크, 도로 지도, 의존성 그래프)는 **희소(sparse)**하므로, adjacency list가 엄청난 공간을 절약하고 BFS/DFS 같은 순회를 빠르게 합니다.

트레이드오프를 알면 실수로 O(V²) 메모리를 쓰는 대신 그래프 알고리즘을 효율적으로 유지하는 표현을 고를 수 있습니다.

	Adjacency list	Adjacency matrix
공간	O(V + E)	O(V²)
간선 존재?	O(degree)	O(1)
이웃 순회	O(degree)	O(V)
적합한 경우	희소 그래프	밀집 그래프