인접 리스트: 희소한 그래프를 필요한 관계만 저장하기
인접 리스트는 각 정점에 연결된 이웃들을 목록으로 저장하는 그래프 표현이다. 정점 A의 목록을 보면 A에서 바로 이동할 수 있는 정점과 간선 정보를 알 수 있다. 없는 간선까지 공간을 확보하는 인접 행렬과 달리 실제 관계 수에 맞춰 저장한다.
무방향 간선은 양 끝 정점의 이웃 목록에 각각 기록된다.
방향에 따라 저장 횟수가 다르다
방향 간선 A→B는 보통 A의 목록에 B를 한 번 넣는다. 무방향 간선 A—B는 A에 B, B에 A를 넣어 두 방향을 표현한다. 가중치가 있으면 (이웃, 가중치)를 저장한다. 평행 간선을 허용하면 같은 이웃이 여러 번 나올 수 있다.
정점 수 V, 간선 수 E인 그래프의 저장 공간은 O(V+E)다. 무방향 그래프에서 항목이 2E개여도 상수배이므로 같은 표기를 쓴다. 정점 목록이 별도로 없으면 간선이 없는 고립 정점이 사라질 수 있다는 점도 주의한다.
간선을 추가하고 이웃을 읽기
다음 예는 정점이 0부터 V-1까지인 무방향 그래프다. 배열의 각 칸이 서로 다른 목록이어야 하므로 같은 목록 객체를 반복하는 잘못된 초기화를 피한다.
vertex_count = 4
neighbors = [[] for _ in range(vertex_count)]
def add_undirected_edge(first, second, weight):
neighbors[first].append((second, weight))
neighbors[second].append((first, weight))
add_undirected_edge(0, 1, 7)
add_undirected_edge(0, 2, 3)
for next_vertex, edge_weight in neighbors[0]:
print(next_vertex, edge_weight)
0의 목록은 (1,7),(2,3)이고 3의 목록은 비어 있다. 0의 모든 이웃을 확인하는 시간은 차수 deg(0)에 비례한다. 반면 “0과 3 사이에 간선이 있는가”라는 단일 확인도 단순 목록에서는 0의 목록을 훑어야 한다.
인접 행렬은 간선 유무를 O(1)에 확인하지만 모든 이웃을 찾으려면 행 전체 V칸을 읽는다. 정점 10만 개에 간선 30만 개인 관계는 행렬의 100억 칸을 확보하기보다 인접 리스트가 훨씬 적합할 수 있다. 반대로 거의 모든 정점 쌍이 이어진 밀집 그래프는 차이가 작아진다.
인접 리스트에서 BFS나 DFS는 각 정점과 간선을 일정 횟수만 처리하여 O(V+E)다. 그래프 순회의 결과가 이웃 저장 순서에 따라 달라질 수 있으므로, 특정 출력 순서가 필요하면 목록 정렬 등의 비용을 추가해야 한다.
리스트에 간선을 넣는 일만으로 중복 금지나 정렬이 보장되는 것은 아니다. 빈번한 간선 존재 확인에는 이웃 집합이나 맵을 사용할 수 있고, 삭제가 많으면 위치 관리가 필요하다. 표현 방식은 알고리즘이 자주 수행할 작업에 맞춰 선택해야 한다.
간선을 삭제할 때 무방향 관계라면 양쪽 목록을 함께 바꿔야 한다. 한쪽만 지우면 같은 저장소가 방향에 따라 서로 다른 그래프를 표현하게 된다.