그래프 표현하기: 리스트냐 행렬이냐

"그래프를 순회하려면 먼저 저장해야 해. 그런데 저장하는 두 방식이 정반대 거래를 하거든. 잘못 고르면 노드 백만 개짜리 소셜 네트워크가 빈 칸 1조 개를 잡아먹어."

인접 리스트: 각 정점이 이웃을 나열

가장 흔한 표현이야. 각 정점을 그 이웃 목록에 대응시키는 딕셔너리나 리스트를 쓰는 거지. {"A": ["B", "C"], "B": ["A"], ...} 이런 식으로. 공간은 O(V + E)야. 정점을 한 번씩, 간선을 한 번씩 저장하니까. 어떤 정점의 이웃을 훑는 건 빠르고 직접적이고. "A에서 B로 가는 간선이 있나?"를 확인하려면 A의 이웃 목록을 훑어야 하니 O(차수)가 들어. 간선 수가 가능한 최대치인 V²보다 훨씬 적은 희소 그래프에서 기본으로 쓰는데, 현실의 그래프는 거의 다 여기 해당해. 사람의 친구가 수백 명이지 수백만 명은 아니잖아.

인접 행렬: 예/아니오 격자

다른 방법은 V×V 격자를 쓰는 거야. 셀 [i][j]에 i에서 j로 가는 간선이 있으면 1, 없으면 0을 넣지. 가중치가 있으면 그 값을 넣고. 간선 조회가 O(1)이야. 셀을 인덱싱하면 끝이니까. 그런데 공간은 간선이 아무리 적어도 O(V²)고, 한 정점의 이웃을 훑으려면 그 행 전체를 봐야 하니 O(V)가 들어. 행렬은 간선이 많은 조밀한 그래프나 "이 둘 사이에 간선 있어?"를 쉴 새 없이 물어야 할 때 빛나. 반대로 크고 희소한 그래프에는 재앙이야. 정점이 백만 개면 셀이 1조 개 필요한데 거의 다 0이거든.

인접 리스트는 공간이 O(V+E)고, 이웃 순회가 빠르고, 간선 확인이 O(차수)야. 현실의 그래프 대부분이 희소하니까 이게 기본값이지. 인접 행렬은 공간이 O(V²)고 간선 확인이 O(1)이야. 조밀한 그래프이거나 간선 존재 여부를 상수 시간에 물어야 할 때만 써.

세 번째 선택지, 그리고 가중치

더 단순한 세 번째 형태가 간선 리스트야. 그냥 (u, v) 쌍을, 가중치가 있으면 (u, v, weight)를 늘어놓은 목록이지. 빠른 조회는 없지만 어떤 알고리즘은 정확히 이 형태를 원해. 다음 트랙에 나올 Kruskal 최소 신장 트리가 가중치 순으로 정렬된 간선을 처리하니까, 간선 리스트가 자연스러운 입력이거든. 가중치 그래프도 두 주요 표현에 쉽게 얹혀. 인접 리스트에는 (neighbor, weight)를 저장하고, 행렬에는 셀에 가중치를 넣으면 돼. 표현을 고르는 것도 문제를 푸는 과정의 일부고, 돌릴 알고리즘이 형태를 결정해 버리기도 해.

피파의 고백

첫 그래프를 인접 행렬로 만들었어. 격자가 그리기 쉬웠거든. 노드 다섯 개짜리 장난감에서는 잘 돌아갔지. 그러다 노드 수만 개짜리 실제 네트워크로 키우니까 셀이 수억 개인 행렬을 잡으려 드는 걸 보게 됐어. 거의 다 0인 채로. 아빠의 교정은 한 단어였어. "희소." 현실의 그래프는 대부분 비어 있으니까 존재하는 간선만 저장하는 리스트가 맞는 집인 거야. 행렬이 틀린 게 아니었어. 실제 데이터의 모양에 안 맞았던 거지.

Code

인접 리스트와 인접 행렬·python

# *같은* 작은 무방향 그래프, 두 방법.
#   A — B
#   |   |
#   C — D

# 인접 리스트: O(V+E) 공간, 희소-그래프 기본.
adj_list = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"],
}
print("A's neighbors:", adj_list["A"])              # 빠르고 직접
print("edge A-D?    :", "D" in adj_list["A"])        # O(차수) 훑기 -> False

# 인접 행렬: O(V^2) 공간, O(1) 엣지 조회.
idx = {"A": 0, "B": 1, "C": 2, "D": 3}
M = [[0]*4 for _ in range(4)]
for u, v in [("A","B"), ("A","C"), ("B","D"), ("C","D")]:
    M[idx[u]][idx[v]] = M[idx[v]][idx[u]] = 1        # 무방향 -> 대칭
print("edge A-B?    :", M[idx["A"]][idx["B"]] == 1)  # O(1) -> True
# 정점 1,000,000 개면: 리스트는 ~엣지 저장. 행렬은 10^12 셀 필요.

Exercise

트위터를 모델링한다고 해 보자. 사용자가 5억 명쯤 되고 각자 수백 명을 팔로우해. 어느 표현을 고르고 왜 그럴까? 인접 리스트와 행렬의 대략적인 메모리 규모를 계산해 보고, 왜 한쪽이 여기서 물리적으로 불가능한지 설명해. 그리고 행렬이 오히려 나은 선택이 되는 건 언제일까?

Hint

인접 리스트는 O(V+E)라 5억 사용자에 각자 수백 개 간선이니 크긴 해도 감당할 수 있어. 행렬은 O(V²)라 (5×10^8)² = 2.5×10^17 셀이 필요한데 이건 물리적으로 불가능하고. 행렬이 이기는 건 작고 조밀한 그래프이거나 간선 존재 여부를 O(1)로 계속 물어야 할 때뿐이야.

인접 리스트: 각 정점이 이웃을 나열

인접 행렬: 예/아니오 격자

세 번째 선택지, 그리고 가중치

피파의 고백

Code

External links

Exercise

Progress

댓글 0