인접 리스트와 인접 행렬 (adjacency list and adjacency matrix)
쉽게 풀면
그래프를 컴퓨터에 표현하는 방법은 크게 두 가지다. 인접 행렬은 정점이 n개면 n×n 크기의 표를 만들어 (i, j) 칸에 정점 i와 j가 연결되어 있는지를 표시한다. 두 정점이 연결되어 있는지 확인하는 것은 즉시 가능하지만, 정점 수가 많고 간선이 적은 그래프에서는 대부분의 칸이 빈 채로 메모리를 낭비하게 된다. 인접 리스트는 각 정점마다 자신과 연결된 이웃들의 목록만 저장하기 때문에 간선이 적은 희소 그래프에서 메모리를 훨씬 절약할 수 있다.
왜 중요한가
그래프 표현 방식의 선택은 그 위에서 동작하는 탐색, 최단 경로, 신장 트리 등 거의 모든 그래프 알고리즘의 시간·공간 복잡도를 좌우한다. 실제 데이터(소셜 네트워크, 도로망, 지식 그래프 등)는 대부분 정점 수에 비해 간선이 훨씬 적은 희소 그래프이기 때문에, 대규모 그래프를 다루는 논문에서는 자료구조 선택 자체가 실험 규모의 한계와 직결된다. 그래서 방법론 절에서 어떤 표현을 썼는지, 그로 인한 복잡도가 어떻게 되는지를 명시하는 경우가 많다.
논문에서는 이렇게 쓰입니다
그래프 알고리즘 구현 시 자료구조 선택이 메모리와 시간 복잡도에 미치는 영향을 논의할 때 쓰인다.
밀집도가 높거나 빠른 연결 조회가 중요한 경우, 메모리 비용을 감수하고 인접 행렬을 선택하는 사례를 보여준다.
그래프 신경망(GNN) 관련 논문에서 이웃 정보를 효율적으로 순회하기 위한 자료구조로 인접 리스트가 사용되는 예시다.
조금 더 깊게 보면
실무에서는 인접 리스트를 배열의 배열이나 해시맵으로 구현하는 경우가 많으며, 대규모 희소 그래프에서는 압축된 형태인 CSR(Compressed Sparse Row) 방식을 함께 쓰기도 한다. 가중치가 있는 그래프라면 이웃 정점뿐 아니라 간선 가중치도 함께 저장해야 하므로 자료구조 설계가 조금 더 복잡해진다. 두 방식의 성능 차이는 정점 연결 여부 조회(인접 행렬이 유리), 특정 정점의 이웃 전체 순회(인접 리스트가 유리)처럼 어떤 연산이 알고리즘에서 더 빈번한지에 따라 갈리므로, 논문을 읽을 때는 저자가 어떤 연산을 기준으로 자료구조를 골랐는지 함께 확인하는 것이 도움이 된다.
주의할 점
밀집 그래프(간선이 정점 수의 제곱에 가까운)에서는 인접 행렬이, 희소 그래프에서는 인접 리스트가 유리하다는 트레이드오프를 고려해 선택해야 한다.