입력 그대로 보관
(1, 2)
(1, 3)
(3, 4)
(4, 2)
정렬, 파싱, Kruskal 계열처럼 간선 단위 처리가 쉬워집니다.
같은 간선도 표현에 따라 비용이 달라진다
입력 간선은 하나지만 저장 방식은 여러 가지입니다. 순회가 많은지, 간선 존재 질의가 많은지, 가중치와 중복 정책이 있는지에 따라 모델을 고릅니다.
인접 순회 중심
12, 3
2empty
34
42
BFS/DFS처럼 이웃을 훑는 문제에서 실제 존재하는 간선만 저장해 O(V+E) 공간으로 순회합니다.
존재 질의 중심
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 1 |
| 4 | 0 | 1 | 0 | 0 |
exists(u, v)가 많은 작은 밀집 그래프에서 유리합니다.
E가 V보다 크게 늘지 않으면 인접 리스트가 기본 선택입니다.
간선 확인이 반복되면 O(1) 행렬 질의가 이득입니다.
거리, 용량, 중복 간선은 구조체나 맵으로 정책을 분리합니다.