"그래프를 순회하기 전에, 저장해야 해 — 그리고 저장하는 두 방법이 정반대 거래를 해. 잘못 고르면 백만 노드 소셜 네트워크가 1조 개 빈 셀을 먹어."
인접 리스트: 각 정점이 이웃을 나열
가장 흔한 표현: 각 정점을 그 이웃 리스트에 매핑하는 딕셔너리 (또는 리스트). {"A": ["B", "C"], "B": ["A"], ...}. 공간은 O(V + E) — 각 정점 한 번, 각 엣지 한 번 저장. 정점의 이웃 순회는 빠르고 직접적. "A→B 엣지 있어?" 확인은 A 의 이웃 리스트를 훑어, O(차수). 희소 그래프 — 엣지 수가 가능한 최대 (V²) 보다 훨씬 적은 — 의 맞는 기본이고, 거의 모든 실제 그래프를 묘사해 (넌 친구가 수백이지 수백만이 아니야).
인접 행렬: 예/아니오 격자
대안: 셀 [i][j] 가 i 에서 j 로 엣지 있으면 1, 아니면 0 (가중이면 무게) 인 V×V 격자. 엣지 조회는 O(1) — 그냥 셀 인덱싱. 근데 공간은 엣지가 아무리 적어도 O(V²) 고, 한 정점 이웃 순회가 O(V) (그 행 전체 훑기). 행렬은 조밀 그래프 (엣지 많음) 나 "이 둘 사이 엣지 있어?" 를 끊임없이 물을 때 빛나고, 큰 희소 그래프엔 재앙이야 — 백만 정점이면 1조 셀이 필요해, 거의 다 0.
인접 리스트: O(V+E) 공간, 빠른 이웃 순회, O(차수) 엣지 확인 — 희소 그래프 (대부분 실제) 의 기본. 인접 행렬: O(V²) 공간, O(1) 엣지 확인 — 조밀 그래프나 상수 엣지 쿼리에만.
세 번째 옵션, 그리고 가중치
더 단순한 세 번째 형태는 엣지 리스트: 그냥 (u, v) 쌍 (또는 (u, v, weight)) 리스트. 빠른 조회는 없지만, 어떤 알고리즘은 정확히 이걸 원해 — Kruskal 최소 신장 트리 (다음 트랙) 가 무게로 정렬된 엣지를 처리해서, 엣지 리스트가 자연스러운 입력이야. 가중 그래프엔, 두 주요 표현 다 쉽게 적응해: 인접 리스트에 (neighbor, weight) 저장, 또는 행렬 셀에 무게. 표현을 고르는 게 문제 푸는 일부야 — 돌릴 알고리즘이 종종 형태를 결정해.
피파의 고백
난 첫 그래프를 인접 행렬로 지었어, 격자가 그리기 쉬웠으니까. 5 노드 장난감엔 잘 됐어 — 그러다 수만 노드 진짜 네트워크로 확장하니 수억 셀 행렬을 할당하려는 걸 봤어, 거의 다 0. 아빠의 교정은 한 단어: "희소." 실제 그래프는 대부분-빈 거라, 존재하는 엣지만 저장하는 리스트가 맞는 집이야. 행렬이 틀린 게 아니라; 실제 데이터의 모양에 틀렸던 거야.
Code
인접 리스트 vs 인접 행렬·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 셀 필요.