인접 리스트

인접 리스트는 그래프에서 누가 누구와 이어져 있는지를 항목마다 목록으로 적어 둡니다. 이어진 상대만 적습니다. 이어지지 않은 짝은 적지 않습니다. 그래서 항목은 많은데 연결은 드문 그래프를 적은 메모리로 담습니다.

상세

이 절은 다섯 사람의 친구 관계를 인접 리스트에 담아 보고 그 모양부터 봅니다. 그 모양 위에서 이웃을 꺼내는 일과 이어졌는지 묻는 일이 어떻게 도는지 따라간 뒤 파이썬 코드로 옮겨 봅니다.

뒤에서는 방향과 가중치가 붙은 그래프로 넓힙니다. 비용은 모든 짝마다 칸을 두는 표, 곧 인접 행렬과 견줍니다. 끝으로 이웃 목록을 무엇으로 담는지, 인접 리스트가 맞는 그래프와 안 맞는 그래프가 무엇인지 봅니다.

그래프와 이웃

그래프는 무엇과 무엇이 이어져 있는지를 담는 자료구조입니다. 이어지는 항목 하나를 노드라고 부릅니다. 두 노드를 잇는 선 하나는 간선이라고 부릅니다.

다섯 사람 A · B · C · D · E 의 친구 관계를 그래프로 그리면 이렇습니다. A 는 B, C 와 친구입니다. B 는 C 와 친구입니다. C 는 D 와 친구입니다. E 는 아무와도 친구가 아닙니다.

flowchart TD
    A["A"] --- B["B"]
    A --- C["C"]
    B --- C
    C --- D["D"]
    E["E"]

간선 하나로 바로 이어진 두 노드를 서로 인접하다고 합니다. 인접한 노드를 그 노드의 이웃이라고 부릅니다. C 의 이웃은 A · B · D 셋입니다. A 와 D 는 C 를 거쳐야 닿으므로 서로 이웃이 아닙니다.

인접 리스트라는 이름은 이 낱말에서 왔습니다. 노드마다 자기와 인접한 노드의 목록을 하나씩 들고 있다는 뜻입니다.

노드마다 이웃 목록 하나

인접 리스트는 노드마다 칸을 하나씩 둡니다. 그 칸에 그 노드의 이웃을 늘어놓은 목록을 붙입니다. 이 목록을 이웃 목록이라고 부르겠습니다.

flowchart TD
    subgraph 칸["노드마다 칸 하나"]
        A["A"]
        B["B"]
        C["C"]
        D["D"]
        E["E"]
    end
    A --> LA["B · C"]
    B --> LB["A · C"]
    C --> LC["A · B · D"]
    D --> LD["C"]
    E --> LE["비어 있음"]

위 상자 안이 노드마다 하나씩 둔 칸입니다. 칸 아래에 매달린 상자가 그 노드의 이웃 목록입니다. E 는 이웃이 없어서 목록이 비어 있습니다. 이웃이 없는 노드도 칸은 하나 차지합니다.

이어지지 않은 짝은 어디에도 적히지 않습니다. A 의 목록에 D 가 없다는 것이 곧 A 와 D 가 이어져 있지 않다는 뜻입니다.

간선 하나는 두 번 적힙니다. A 와 B 를 잇는 간선은 A 의 목록에 B 로, B 의 목록에 A 로 들어갑니다. 그래서 간선 넷을 담으면 목록에 적힌 이웃은 모두 여덟 개입니다.

이웃 꺼내기와 이어짐 묻기

한 노드의 이웃을 꺼낼 때는 그 노드의 칸을 찾아 목록을 읽습니다. 다른 노드의 목록은 들여다보지 않습니다. 걸리는 시간은 그 목록의 길이만큼입니다.

한 노드에 붙은 간선 수를 그 노드의 차수라고 부릅니다. 이웃 목록의 길이가 곧 차수입니다. C 의 차수는 3 이고 E 의 차수는 0 입니다.

「A 와 D 가 이어졌나」를 물으면 A 의 목록을 앞에서부터 훑으며 D 를 찾습니다. D 가 없으면 목록을 끝까지 보고 나서야 없다고 답합니다. 이 물음에는 A 의 차수만큼 시간이 걸립니다.

두 노드 중 어느 쪽 목록을 훑어도 답은 같습니다. 차수가 작은 쪽 목록을 훑으면 덜 봅니다.

간선을 새로 넣을 때는 두 노드의 목록 끝에 서로를 붙입니다. 목록을 훑을 필요가 없어서 금방 끝납니다. 간선을 뺄 때는 두 목록에서 상대를 찾아 지워야 하므로 차수만큼 걸립니다.

그래프 전체를 훑으면 칸을 한 번씩 봅니다. 목록에 적힌 이웃도 한 번씩 봅니다. 드는 시간은 노드 수와 목록에 적힌 이웃 수를 더한 만큼입니다.

파이썬으로 담은 인접 리스트

파이썬에서는 딕셔너리 하나로 담습니다. 키가 노드이고 값이 이웃 목록입니다. 자바라면 Map<String, List<String>> 이 같은 모양입니다.

graph = {
    "A": ["B", "C"],
    "B": ["A", "C"],
    "C": ["A", "B", "D"],
    "D": ["C"],
    "E": [],
}

앞에서 본 이웃 꺼내기와 이어짐 묻기를 이 딕셔너리로 해 봅니다.

graph["C"]          # ['A', 'B', 'D']
len(graph["C"])     # 3
"B" in graph["A"]   # True
"D" in graph["A"]   # False

graph["C"] 가 이웃 꺼내기이고 len 이 차수입니다. in 은 목록을 앞에서부터 훑어 찾으므로 이어짐 묻기가 차수만큼 걸립니다.

간선을 넣는 함수는 두 목록에 한 번씩 붙입니다.

def add_edge(g, u, v):
    g[u].append(v)
    g[v].append(u)

한쪽 목록에만 붙이면 A 는 B 를 친구로 아는데 B 는 A 를 모르는 그래프가 됩니다. 이런 실수는 모든 목록에 적힌 이웃 수를 더해 보면 드러납니다. 제대로 붙였으면 이 합이 간선 수의 두 배입니다. 한쪽에만 붙인 간선이 있으면 두 배에서 어긋납니다.

sum(len(n) for n in graph.values())  # 8

간선이 넷이므로 8 이 맞습니다.

방향이 있는 그래프

간선에 방향이 붙은 그래프를 방향 그래프라고 합니다. 「주문 서비스가 결제 서비스를 부른다」는 주문에서 결제로 가는 간선 하나입니다. 결제가 주문을 부른다는 뜻은 담겨 있지 않습니다.

방향 그래프에서는 간선을 출발 노드의 목록에만 적습니다. 간선 하나가 목록 한 곳에만 들어가므로 목록에 적힌 이웃 수가 간선 수와 같습니다.

calls = {
    "주문": ["결제", "재고"],
    "결제": ["알림"],
    "재고": [],
    "알림": [],
}
calls["주문"]  # ['결제', '재고']

「주문이 부르는 서비스」는 주문의 목록 하나로 답합니다. 반대로 「결제를 부르는 서비스」는 어느 목록에도 모여 있지 않습니다. 모든 목록을 훑어 결제가 들어 있는 목록을 찾아야 합니다.

이 물음이 잦으면 간선을 거꾸로 뒤집은 목록을 하나 더 둡니다. 노드마다 「나에게 들어오는 간선」을 적은 목록입니다. 대가는 둘입니다. 메모리를 두 배로 씁니다. 간선을 넣을 때마다 두 곳을 고쳐야 합니다.

가중치가 붙은 그래프

간선마다 거리 · 요금 · 걸리는 시간 같은 수가 붙을 때가 있습니다. 이 수를 가중치라고 합니다. 가중치가 있으면 목록에 상대 이름만 적지 않고 「상대와 가중치」의 짝을 적습니다.

cost = {
    "주문": [("결제", 40), ("재고", 15)],
    "결제": [("알림", 5)],
    "재고": [],
    "알림": [],
}
cost["주문"][1]  # ('재고', 15)

주문에서 재고로 가는 호출에 15 가 붙어 있습니다. 가장 싼 길을 찾는 절차는 목록에서 이 짝을 하나씩 꺼내 상대와 가중치를 함께 봅니다.

인접 행렬과 견준 비용

이 절은 인접 리스트가 드는 시간과 공간을 다른 대표 방법과 한 표에 놓고 견줍니다. 먼저 비용을 적는 표기 둘을 봅니다. 그다음 견줄 상대를 소개한 뒤 표로 갑니다.

비용은 노드 수와 간선 수에 따라 달라집니다. 짧게 적으려고 노드 수는 V 로, 간선 수는 E 로 씁니다. V 는 노드의 다른 이름인 정점(vertex)에서, E 는 간선(edge)에서 딴 글자입니다.

그래프가 커질 때 비용이 어떻게 늘어나는지는 빅오 표기법으로 적습니다. 늘어나는 꼴만 남기고 자잘한 차이는 버리는 적는 법입니다. O(V+E) 는 드는 시간이나 공간이 V 와 E 를 더한 값에 비례해 늘어난다는 뜻입니다.

O(1) 은 그래프가 커져도 드는 시간이 그대로라는 뜻입니다. O(차수) 는 그 노드의 이웃 목록 길이만큼 걸린다는 뜻입니다.

그래프를 담는 또 다른 대표 방법이 인접 행렬입니다. 앞에서 본 「모든 짝마다 칸을 하나씩 두는 표」가 바로 이것입니다.

노드를 가로와 세로에 늘어놓은 표를 만듭니다. 칸마다 두 노드가 이어졌는지를 적습니다. 다섯 사람이면 25 칸입니다. 그중 여덟 칸만 「이어졌다」입니다.

표에서 행렬이 이기는 것은 이어짐 묻기와 간선 빼기입니다. 두 노드가 만나는 칸 하나만 보면 됩니다. 리스트가 이기는 것은 공간 · 이웃 꺼내기 · 전체 훑기입니다. 행렬은 이웃이 몇 없어도 한 줄 V 칸을 전부 봐야 합니다.

간선이 가능한 짝의 수보다 훨씬 적은 그래프를 희소 그래프라고 부릅니다. 사용자가 백만 명이고 한 사람이 친구 100명과 이어져 있다고 합시다. 인접 행렬은 1조 칸이 듭니다. 인접 리스트는 목록에 적힌 이웃 1억 개로 끝납니다.

반대로 거의 모든 짝이 이어진 그래프를 밀집 그래프라고 부릅니다. 이때는 E 가 V² 에 가까워서 공간 차이가 줄어듭니다. 이어짐을 칸 하나로 답하는 행렬의 이점만 남습니다.

이웃 목록을 담는 자료구조

이름의 「리스트」는 목록이라는 뜻입니다. 이웃 목록을 무엇으로 담을지는 따로 고릅니다. 흔히 쓰는 것은 셋입니다.

연결 리스트는 값마다 다음 값을 가리키는 포인터를 하나씩 둡니다. 새 값을 맨 앞에 붙이는 일이 목록 길이와 상관없이 한 번에 끝납니다. 대신 값이 메모리 여기저기에 흩어집니다.

동적 배열은 값을 메모리에 붙여서 늘어놓습니다. 칸이 차면 더 큰 곳으로 옮깁니다. 파이썬의 리스트가 이 모양입니다. 옮기는 일이 가끔만 일어나서 끝에 붙이기는 평균으로 치면 금방 끝납니다.

붙어 있는 값을 차례로 읽으면 빠릅니다. 프로세서가 메모리를 한 덩어리씩 가져오기 때문에 이웃한 값은 이미 가져온 덩어리 안에 있습니다. 이 성질을 캐시 지역성이라고 합니다. 목록을 훑는 일이 잦은 인접 리스트에서 동적 배열이 흔히 쓰이는 이유입니다.

해시테이블로 만든 집합은 값을 키로 흩어 담습니다. 「이 이웃이 있나」를 목록을 훑지 않고 평균 O(1) 에 답합니다. 대신 빈칸을 섞어 두어서 메모리를 더 씁니다.

셋 다 이웃을 꺼내는 비용은 차수만큼입니다. 갈리는 것은 이어짐을 묻는 비용과 훑는 속도입니다.

인접 리스트가 맞는 그래프

그래프를 다루는 절차 대부분은 「노드 하나를 꺼내 그 이웃을 모두 본다」를 되풀이합니다. 인접 리스트는 이웃 꺼내기를 목록 하나 읽기로 끝내므로 이런 절차에 맞습니다.

대표로 너비 우선 탐색을 봅니다. 시작 노드에서 가까운 노드부터 한 겹씩 넓혀 가는 탐색입니다. 노드 하나를 꺼낼 때마다 그 노드의 이웃 목록을 읽어 다음에 볼 노드를 정합니다. 인접 리스트에서는 칸과 목록에 적힌 이웃을 한 번씩만 보므로 전체가 O(V+E) 로 끝납니다.

같은 꼴로 도는 절차로 깊이 우선 탐색 · 다익스트라 알고리즘 · 위상 정렬이 있습니다. 이 절차들을 설명할 때는 그래프가 인접 리스트로 담겨 있다고 두고 시작하는 경우가 많습니다.

백엔드에서 만나는 그래프도 대개 희소합니다. 앞의 주문 서비스는 결제와 재고 둘만 부릅니다. 서비스가 수백 개여도 한 서비스의 목록에는 이렇게 이름 몇 개뿐입니다. 이런 의존성 그래프는 서비스마다 부르는 목록을 하나씩 들고 있는 모양이라 그대로 인접 리스트가 됩니다.

인접 리스트가 안 맞는 그래프

거의 모든 짝이 이어진 밀집 그래프에서 「이 둘이 이어졌나」를 자주 묻는다면 인접 행렬이 맞습니다. 공간 차이는 크지 않습니다. 물음마다 칸 하나로 답합니다.

간선을 한 줄에 하나씩 「출발 노드와 도착 노드」의 짝으로 늘어놓는 방법도 있습니다. 이것을 간선 리스트라고 부릅니다. 이웃을 꺼내려면 전체를 훑어야 합니다. 대신 간선 전체를 한 번에 정렬하기는 쉽습니다.

크루스칼 알고리즘은 간선을 가중치가 작은 순서로 정렬해 하나씩 봅니다. 노드마다 이웃을 꺼내는 일이 없으므로 인접 리스트보다 간선 리스트가 맞습니다.

관련 항목

인접 리스트가 속하는 상위 분류

자료구조 · 그래프 · 그래프 표현 · 비선형 자료구조

인접 리스트를 이루는 구성 요소

노드 · 정점 · 간선 · 이웃 · 차수 · 가중치

이웃 목록을 담는 자료구조

연결 리스트 · 동적 배열 · 배열 · 해시테이블 · 집합 · 딕셔너리 · 맵 · 포인터

인접 리스트와 겨루는 그래프 표현 방식

인접 행렬 · 간선 리스트 · 압축 희소 행 · 순방향 스타 · 희소 행렬

인접 리스트로 담는 그래프의 종류

방향 그래프 · 무방향 그래프 · 가중 그래프 · 희소 그래프 · 밀집 그래프 · DAG · 전치 그래프 · 다중 그래프

인접 리스트 위에서 도는 알고리즘

너비 우선 탐색 · 깊이 우선 탐색 · 다익스트라 알고리즘 · 위상 정렬 · 최단 경로 · 크루스칼 알고리즘 · 프림 알고리즘 · 강한 연결 요소

인접 리스트로 담는 관계

의존성 그래프 · 호출 그래프 · 소셜 그래프 · 그래프 데이터베이스 · 빌드 그래프

인접 리스트의 비용을 재는 지표

시간 복잡도 · 공간 복잡도 · 빅오 표기법 · 캐시 지역성