그래프 표현 방식: 인접 리스트·행렬·CSR 선택 기준과 구현
그래프의 희소성, 갱신 빈도, 질의와 분석 패턴에 따라 인접 리스트·인접 행렬·CSR을 선택하는 기준과 Python 구현 방법을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
그래프의 형태보다 작업 방식이 표현을 결정한다
그래프는 정점 집합 V와 간선 집합 E로 이루어진 G = (V, E)로 표현한다. 방향성, 가중치, 멀티그래프와 자가루프 허용 여부도 모델에 포함된다. 하지만 구현 단계에서는 이 정의만으로 충분하지 않다. 같은 그래프라도 이웃을 자주 순회하는지, 간선 존재 여부를 반복 확인하는지, 갱신이 많은지에 따라 적합한 저장 구조가 달라진다.
간선 수 m이 n^2 수준이면 밀집 그래프이고, m ≪ n^2이면 희소 그래프다. 대규모 실무 그래프는 대체로 희소하다. 구축 뒤 질의와 분석이 중심인 정적 그래프와, 정점·간선의 추가와 삭제가 반복되는 동적 그래프도 구분해야 한다.
선택 대상이 되는 연산은 이웃 순회, 간선 존재 질의, 정점·간선 삽입과 삭제, BFS·DFS 같은 전체 탐색, 최단 경로·중앙성·연결성 계산까지 넓다.
희소 그래프에서 출발하기 좋은 인접 리스트
인접 리스트는 각 정점마다 연결된 이웃 정점 목록을 둔다. 목록은 리스트나 벡터로 만들 수 있고, 간선 존재 여부를 빠르게 확인해야 한다면 해시셋을 쓸 수 있다. 공간 복잡도는 O(n + m)이므로 희소 그래프에 잘 맞는다.
이웃 u를 순회하는 비용은 O(deg(u))다. 리스트 기반 구현에서 간선 존재 질의는 O(deg(u))이고, 해시셋 기반은 평균 O(1)이다. 해시셋은 삽입과 삭제에도 유리하지만, 밀집 그래프에서는 캐시 비지역성과 메모리 단편화가 문제가 될 수 있다.
빠른 간선 질의가 필요한 인접 행렬
인접 행렬은 n×n 공간에 간선 존재 여부나 가중치를 기록한다. 비트, 바이트, 수치형 가운데 필요한 표현을 골라 사용할 수 있다. 공간 복잡도는 O(n^2)이므로 작은 그래프나 밀집 그래프에 적합하다.
행렬의 한 칸을 확인하면 되므로 간선 존재 질의는 O(1)이다. 반면 한 정점의 이웃을 찾으려면 행을 훑어야 하므로 O(n)이 든다. 희소한 대형 그래프에는 공간 낭비가 크지만, 연속된 메모리 구조와 벡터화·선형대수 연산에는 강점이 있다.
배치 분석에는 간선 리스트와 CSR/CSC
간선 리스트는 (u, v, w) 튜플을 배열로 보관하는 방식이다. 스트리밍 적재, 정렬, 배치 처리에 편하다. CSR/CSC는 row_ptr, col_idx, values의 연속 배열로 이웃 관계를 압축하며, 공간 복잡도는 O(n + m)이다.
CSR/CSC는 PageRank, SpMV, GNN처럼 대규모 배치 분석이 중심인 작업에서 유리하다. 연속 메모리 덕분에 캐시 친화적이고 벡터화, 멀티스레딩, GPU 가속에 맞추기 쉽다. 대신 간선이나 정점이 자주 변하면 재빌드 비용이 크므로 읽기 중심 워크로드에 적합하다.
발생 행렬은 n×m 공간에서 정점과 간선의 관계를 나타낸다. 흐름, 전기회로, 보존법칙 모델링처럼 제약식과 최적화 문제를 선형대수로 다룰 때 유용하다. 다만 공간 복잡도가 O(nm)이라 일반적인 탐색이나 질의에는 적합하지 않다.
| 표현 방식 | 공간 효율 | 간선 존재 질의 | 이웃 순회 | 삽입/삭제 | 전 그래프 탐색 | 확장성/캐시 |
|---|---|---|---|---|---|---|
| 인접 리스트 | 매우 우수(희소) | O(deg) 또는 O(1, 해시) |
O(deg) |
빠름 | 우수 | 중간(포인터/해시 오버헤드) |
| 인접 행렬 | 열악(희소), 양호(밀집) | O(1) |
O(n) |
느림 | 중간 | 양호(연속 메모리) |
| 간선 리스트 | 우수 | O(m) |
O(m) 전처리 필요 |
매우 빠름 | 전처리 후 우수 | 양호(연속 배열) |
| CSR/CSC | 매우 우수(희소) | O(log deg) 이진탐색 또는 색인 |
O(deg) |
느림(재빌드) | 매우 우수 | 우수(연속, 벡터화) |
희소성·갱신·분석 방식으로 고르기
희소하면서 갱신이 빈번하면 인접 리스트를 우선 검토한다. 희소하지만 정적이고 분석이 중심이면 CSR/CSC가 맞는다. 작고 밀집된 그래프에서 간선 질의가 핵심이면 인접 행렬이 단순하다. 대규모 파이프라인에서는 간선 리스트로 수집한 뒤 주기적으로 CSR을 재구축하는 방식을 쓸 수 있다.
Python으로 보는 저장 구조와 연산
예시는 Python 3.10+를 전제로 하며, 정점 ID는 0..n-1 정수 인덱스라고 가정한다. CSR 예시에는 numpy 1.26+와 scipy 1.11+가 필요하다.
인접 리스트에서 BFS 수행하기
# 환경: Python 3.10+
from collections import deque
class GraphAdjList:
def __init__(self, n: int, directed: bool = False, fast_membership: bool = True):
self.n = n
self.directed = directed
# fast_membership=True: set 기반(간선 존재 O(1)), False: list 기반(메모리 절약)
self.adj = [set() if fast_membership else [] for _ in range(n)]
self.set_mode = fast_membership
def add_edge(self, u: int, v: int):
self._check(u); self._check(v)
if self.set_mode:
self.adj[u].add(v)
if not self.directed:
self.adj[v].add(u)
else:
self.adj[u].append(v)
if not self.directed:
self.adj[v].append(u)
def has_edge(self, u: int, v: int) -> bool:
self._check(u); self._check(v)
if self.set_mode:
return v in self.adj[u]
return v in self.adj[u] # list: O(deg)
def bfs(self, src: int):
self._check(src)
dist = [-1] * self.n
dist[src] = 0
q = deque([src])
while q:
u = q.popleft()
for v in self.adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)
return dist
def _check(self, u: int):
if not (0 <= u < self.n):
raise IndexError("node out of range")
# 사용 예시
g = GraphAdjList(5, directed=False, fast_membership=True)
edges = [(0,1),(1,2),(2,3),(3,4),(4,0)]
for u, v in edges: g.add_edge(u, v)
print(g.has_edge(0, 4)) # True
print(g.bfs(0)) # 각 정점까지의 최단 거리그래프가 매우 커지면 set 기반 구현은 파이썬 객체 오버헤드 때문에 메모리를 크게 사용할 수 있다. 대규모 데이터는 C/C++ 또는 numpy/scipy 기반 구현을 고려한다.
행렬에서 간선을 바로 확인하기
# 환경: Python 3.10+, numpy 1.26+
import numpy as np
n = 5
A = np.zeros((n, n), dtype=np.bool_) # 무방향 비가중 그래프
edges = [(0,1),(1,2),(2,3),(3,4),(4,0)]
for u, v in edges:
A[u, v] = True
A[v, u] = True # 무방향
def has_edge(u, v):
return bool(A[u, v])
# 이웃 순회: np.where(A[u]) 사용
neighbors_of_0 = np.where(A[0])[0] # array([1,4])n이 매우 커지면 행렬의 메모리 사용량도 급증한다. 비트 압축 라이브러리(bitarray 등)를 사용하는 방법을 고려할 수 있다.
CSR을 만들고 벡터화 연산하기
# 환경: Python 3.10+, numpy 1.26+, scipy 1.11+
import numpy as np
from scipy.sparse import csr_matrix
n = 5
edges = np.array([(0,1),(1,2),(2,3),(3,4),(4,0)], dtype=np.int64)
data = np.ones(len(edges), dtype=np.float64)
A = csr_matrix((data, (edges[:,0], edges[:,1])), shape=(n, n))
A = A + A.T # 무방향
# 전형적 스파스 연산: 한 단계 전파(레벨 동기 BFS 유사)
x = np.zeros(n); x[0] = 1.0
y = A @ x # 이웃 누적
print(y) # 정점 0의 이웃 위치에 양의 값
# PageRank-like(스케치)
d = 0.85
row_sum = np.array(A.sum(axis=1)).flatten()
row_sum[row_sum == 0] = 1
M = csr_matrix(A.multiply(1.0/row_sum) ) # 행 정규화
pr = np.full(n, 1.0/n)
for _ in range(20):
pr = (1-d)/n + d * (M.T @ pr)
print(pr / pr.sum())대규모 갱신이 필요한 경우에는 간선 리스트에 변경을 모으고, 주기적으로 CSR을 재빌드하는 배치 파이프라인을 설계할 수 있다.
그래프 성격에 따른 활용
대규모 소셜·웹 그래프는 희소하고 이웃 순회와 선형대수 가속의 비중이 높으므로 CSR/CSC 또는 인접 리스트를 선택할 수 있다. 실시간 경로 탐색과 라우팅은 간선 업데이트와 빠른 존재 질의가 필요해 인접 리스트의 해시셋 구현이 맞는다.
GNN, PageRank, 삼각형 계수처럼 SpMV와 SpGEMM이 중심인 작업에는 CSR/CSC가 어울린다. 반대로 작은 상태 전이, DP, 비트마스크 기반 문제는 O(1) 질의와 비트 연산 최적화, 단순한 구현을 위해 인접 행렬을 사용할 수 있다.
희소 그래프에서 메모리 차이가 커지는 이유
무방향 희소 그래프에서 n = 1,000,000, 평균 차수 d = 4라고 가정하면 간선 수는 m ≈ n·d/2 = 2,000,000이다.
인접 행렬의 이론적 최소 저장량은 간선당 1비트일 때 n^2 비트, 즉 10^12 비트이며 약 125 GB다. Python bool 또는 byte를 쓰는 실무적 표현에서는 10^12 바이트, 약 1.0 TB 규모가 된다.
인접 리스트는 양방향 저장 시 항목 수가 ≈ 2m = 4,000,000이다. C/CSR에서 4바이트 인덱스만 가정하면 약 16 MB(+ 오버헤드)이며, Python set/list의 오버헤드를 고려하면 수백 MB가 될 수 있다. 희소 그래프에서는 인접 행렬보다 인접 리스트나 CSR이 메모리 측면에서 훨씬 적합하다.
이웃 순회가 많은 워크로드에서는 인접 리스트와 CSR이 캐시 효율 및 선형 접근에서 유리하다. 간선 존재 질의가 빈번하면 인접 행렬 또는 해시셋 기반 인접 리스트를 선택한다. 배치 분석과 병렬 처리에는 CSR/CSC가 SpMV 기반 선형대수 가속의 이점을 제공한다.