그래프 표현을 고르는 기준은 “어떤 그래프인가”보다 “어떤 질의를 어떤 빈도로 실행하는가”입니다. V는 정점 수, E는 저장한 간선 수이며, 방향 그래프에서는 u→v와 v→u가 별개의 사실일 수 있으므로 순방향·역방향 인덱스의 의미를 먼저 분리해야 합니다.
정점 수와 질의 유형
정점 백만 개에 각 정점의 이웃이 평균 세 개라면 모든 정점 쌍을 저장하는 행렬은 매우 큽니다. 실제 간선만 모은 인접 리스트가 자연스럽습니다. 반면 정점 수가 작고 모든 쌍의 연결 여부를 반복 검사한다면 행렬의 단순한 주소 계산이 유리할 수 있습니다.
저장 방식은 알고리즘을 실행하기 위한 비용의 일부입니다. 이웃 전체 순회, 특정 간선 존재 확인, 역방향 탐색, 빈번한 삽입·삭제를 나누어 요구를 정해야 합니다.
먼저 예상하는 최악의 out-degree와 갱신률을 적습니다. 희소하고 순회가 주된 그래프는 실제 간선만 저장하는 편이 유리하지만, 작은 조밀 그래프에서 반복적인 존재 확인이 주된 경우에는 행렬의 O(1) 접근이 전체 단순성을 이길 수 있습니다. “평균 degree”만 보고 최악의 고도 정점을 숨기지 않습니다.
인접 리스트·행렬·CSR의 그래프 표현
방향 간선은 0→1, 0→2, 2→1이고 정점 3은 고립되어 있습니다. 인접 리스트는 [[1,2],[],[1],[]]입니다. 행렬은 16칸 중 세 칸에만 간선이 있습니다. CSR은 각 정점의 시작 위치와 연속 이웃 배열을 분리합니다.
| 배열 | 값 | 의미 |
|---|---|---|
| offsets | [0,2,2,3,3] | 정점 u의 이웃은 [offsets[u],offsets[u+1]) |
| neighbors | [1,2,1] | 모든 출발 정점의 이웃을 순서대로 연결 |
| weights, 선택 | 간선과 같은 길이 | 이웃 배열의 같은 위치에 비용 저장 |
정점 2의 이웃은 neighbors[2:3]=[1]입니다. 정점 1·3은 시작과 끝이 같으므로 빈 구간입니다. 마지막 offset이 E와 같은지 확인하면 전체 배열 경계도 검사할 수 있습니다.
그림을 글로 읽기
- 정점 0: offsets[0:2] = 0,2
- 정점 2: offsets[2:4] = 2,3
- neighbors[0:2]: 1 · 2
- neighbors[2:3]: 1
- 정점 0 → neighbors[0:2]: 이웃 두 개
- 정점 2 → neighbors[2:3]: 이웃 한 개
CSR을 읽는 과정은 u의 offsets 두 값을 읽고, 그 반열린 구간을 neighbors에서 순회하는 두 단계입니다. 예를 들어 u=1이면 [2,2)라 이웃이 없고, u=2이면 [2,3)라 neighbors의 세 번째 값만 읽습니다. offsets 길이가 V+1이 아니거나 마지막 값이 E와 다르면 값이 맞아 보여도 경계 계산이 깨진 상태입니다.
이웃 순회와 특정 간선 조회
| 표현 | 기본 공간 | u의 이웃 순회 | u→v 존재 조회 |
|---|---|---|---|
| 행렬 | O(V²) | 행 전체 O(V) | O(1) |
| 비정렬 인접 리스트 | O(V+E) | O(outdegree(u)) | O(outdegree(u)) |
| 정렬 CSR | O(V+E) | O(outdegree(u)) | 이진 탐색 O(log outdegree(u)) |
리스트 자식을 해시 집합으로 관리하면 평균 존재 조회를 줄일 수 있지만 부가 메모리와 갱신 비용이 듭니다. CSR은 노드별 작은 할당과 포인터를 줄이고 연속 순회를 돕지만, 원소가 인접해 있다는 사실만으로 모든 패턴의 성능이 같지는 않습니다.
비용 0인 간선을 “간선 없음”으로 표현하면 그래프가 달라집니다. 존재 비트·선택 타입·별도 sentinel 등을 사용해야 합니다. 같은 두 정점 사이 여러 간선이 있다면 행렬 한 칸의 최솟값만 남길 때 간선 정체성과 개수를 잃는다는 점도 명시합니다.
CSR 중간 삽입과 후속 offset 이동
정점 1→3을 추가하면 neighbors는 [1,2,3,1], offsets는 [0,2,3,4,4]가 됩니다. 새 값 뒤의 원소를 밀고 뒤 정점의 offset을 갱신해야 합니다. 순회용 압축 구조가 갱신에는 불리할 수 있는 이유입니다.
변경을 delta 맵에 모으고 일정 시점에 새 CSR을 만드는 절충도 있습니다. 읽기는 기본 CSR과 delta의 추가·삭제를 병합해야 하며, 같은 간선의 재삽입·tombstone·중복 규칙이 필요합니다. 새 CSR을 공개할 때 offsets와 neighbors를 따로 바꾸면 독자가 다른 세대의 배열을 섞어 읽을 수 있습니다. 하나의 불변 snapshot 객체로 교체하고 옛 독자가 끝난 뒤 회수하는 방식이 명확합니다.
읽기 snapshot R0를 사용하는 중에 R1을 재구축하면 R0의 offsets와 neighbors는 끝까지 함께 유지되어야 합니다. offsets만 먼저 교체하면 같은 u가 이전 배열의 범위를 새 배열에 적용할 수 있습니다. 따라서 갱신 오류는 단순한 삽입 실패뿐 아니라 “서로 다른 세대의 배열을 읽은 결과”도 별도 진단 항목으로 둡니다.
역방향 인덱스와 out/in 이중 갱신
정점 1의 선행 정점을 찾으려면 out 리스트만으로는 전체를 훑어야 할 수 있습니다. in 리스트를 추가하면 in[1]=[0,2]를 바로 읽습니다. 무방향 간선을 양쪽에 저장하는 것과 방향 그래프의 역인덱스를 함께 유지하는 것은 의미가 다르지만 모두 저장량과 갱신 지점이 늘어납니다.
insertEdge(u,v):
lock(graphWriteLock)
validate_edge_policy(u,v)
prepare_capacity_for_both_indexes()
out[u].insert(v)
in[v].insert(u)
publish_same_graph_version()
unlock(graphWriteLock)
insertEdge(0,1)에서 out[0]만 먼저 바뀌고 in[1] 삽입이 실패하면, 한쪽 인덱스에는 간선이 있고 다른 쪽에는 없는 상태가 됩니다. 이 경우 첫 변경을 되돌리거나 두 인덱스를 모두 준비한 새 snapshot을 만든 뒤 한 번에 공개해야 합니다. 위 코드의 용량 준비만으로 모든 타입의 예외 안전성이 자동으로 생기지는 않습니다. 읽는 쪽도 같은 잠금이나 snapshot 경계를 사용해야 out과 in의 서로 다른 세대를 보지 않습니다.
검증 입력에 0→1, 2→1, 중복 0→1, 자기 간선을 넣고 out에서 복원한 간선 다중집합과 in에서 역으로 복원한 다중집합을 비교합니다. 한쪽만 갱신된 경우 순방향 순회는 성공해 보여도 선행자 질의가 빠지므로, 쓰기 성공 응답 전에 두 인덱스의 동일 version을 확인해야 합니다.
저장 표현 변환 전후의 의미 검증
원본 간선 ID·출발·도착·비용을 기준으로 각 표현을 되돌려 같은 다중집합인지 비교합니다. 고립 정점·자기 간선·0 비용·중복 간선·빈 그래프를 포함합니다. 역인덱스에는 모든 out[u]의 v가 in[v]의 u와 대응하는지 검사합니다.
성능은 이웃 순회와 간선 존재 질의를 따로 측정하고, 갱신률을 높였을 때 CSR 재구축·delta 병합 비용이 어디서 커지는지 확인합니다. 저장소 크기가 작다는 사실만이 아니라 실제 질의와 갱신 계약이 선택의 기준입니다.
실무 선택은 저장 공간의 숫자 하나로 끝내지 않습니다. 순회 latency, 특정 간선 조회 p99, 삽입·삭제 batch 비용, rebuild 중 reader 지연을 각각 측정하고, 빈 그래프·고립 정점·0 비용·평행 간선에서 원본 간선 ID가 보존되는지를 먼저 통과시킨 뒤 성능을 비교합니다.