인접 리스트 (Adjacency List)
쉽게 풀면
친구 관계를 정리한다고 생각해봅시다. 반 학생 30명 전체를 놓고 "누구와 누가 친구인지"를 30×30 표로 만들면 900칸을 다 채워야 하는데, 실제 친구 관계는 몇 개뿐이라 대부분 칸이 비어 있게 됩니다. 대신 각 학생마다 "내 친구는 A, B, C"라는 자기 친구 목록만 적어두면 훨씬 간단하고 공간도 아낄 수 있습니다. 이것이 바로 인접 리스트입니다. 정점(사람)마다 자신과 연결된 정점들의 목록만 들고 있기 때문에, 연결이 드문(희소한) 그래프에서 특히 효율적입니다.
왜 중요한가
실제 세계의 그래프—소셜 네트워크, 도로망, 웹 페이지 링크 구조, 단백질 상호작용 네트워크 등—는 대부분 정점 수에 비해 간선 수가 훨씬 적은 희소 그래프입니다. 이런 그래프를 다루는 논문에서는 메모리와 연산 시간을 아끼기 위한 자료구조 선택이 실험 규모를 좌우하기 때문에, 인접 리스트는 그래프 알고리즘·네트워크 분석·그래프 신경망(GNN) 등 폭넓은 연구에서 기본 전제로 등장합니다. 대규모 그래프를 다루는 시스템 논문에서는 인접 리스트를 어떻게 압축·분산 저장하느냐 자체가 성능을 좌우하는 핵심 설계 문제가 되기도 합니다.
논문에서는 이렇게 쓰입니다
이 문장은 "정점(V)과 간선(E)의 개수에 비례하는 만큼만 메모리를 쓰도록, 연결 정보를 각 정점별 목록 형태로 저장했다"는 뜻입니다. 정점 수가 아무리 많아도 실제 연결(간선)이 적으면 인접 리스트가 표를 통째로 만드는 방식보다 훨씬 적은 메모리를 씁니다.
그래프 신경망(GNN)은 매 학습 단계마다 각 노드의 이웃 노드 정보를 참조해야 하는데, 이때 인접 리스트를 미리 만들어 두면 "이 노드의 이웃이 누구인지"를 표 전체를 뒤지지 않고 바로 꺼내 쓸 수 있어 학습 속도가 대체로 개선됩니다.
도로망 같은 대규모 지리 데이터에서도 교차로(정점)마다 실제로 연결된 도로(간선)만 저장하면 되므로, 인접 리스트에 가중치(이동 시간, 거리 등)를 함께 기록해 최단 경로 탐색 같은 알고리즘의 입력으로 흔히 사용됩니다.
조금 더 깊게 보면
인접 리스트는 구현 방식에 따라 배열의 배열, 연결 리스트의 배열, 혹은 해시 테이블 기반 등 여러 형태로 만들 수 있으며, 논문에서는 이웃 탐색 속도와 메모리 효율의 균형을 위해 구체적인 구현을 선택합니다. 가중치가 있는 그래프에서는 단순히 이웃 정점 번호만이 아니라 (이웃 정점, 가중치) 쌍을 함께 저장하는 형태로 확장되는 경우가 많습니다. 또한 압축 희소 행/열(CSR/CSC) 형식처럼 인접 리스트의 아이디어를 하나의 연속된 배열로 압축해 캐시 효율과 병렬 처리에 유리하게 만든 변형도 대규모 그래프 처리 논문에서 자주 등장합니다. 방향 그래프에서는 나가는 간선과 들어오는 간선을 따로 저장할지(정방향/역방향 인접 리스트) 여부도 알고리즘 설계에서 고려되는 지점입니다.
주의할 점
인접 리스트는 간선이 적은 희소 그래프에는 유리하지만, 두 정점이 연결되어 있는지를 확인하려면 목록을 처음부터 훑어야 해서 인접행렬처럼 한 번에 확인(O(1))할 수는 없습니다. 반대로 간선이 매우 많은 밀집 그래프에서는 인접행렬이 더 단순하고 빠를 수 있으므로, 그래프의 밀도와 자주 하는 연산(연결 확인 vs 전체 순회)에 따라 표현 방식을 선택해야 합니다.