그래프 탐색의 비용은 정점 수 V와 간선 수 E, 그리고 그래프를 어떻게 저장했는지에 따라 정해집니다. 이 장에서는 BFS, DFS, 위상 정렬의 시간과 공간을 분석하고, 표현 방식과 다른 알고리즘과의 차이를 표로 비교합니다.
왜 O(V + E)인가
인접 리스트 위에서 BFS나 DFS를 돌리면 다음 두 가지가 성립합니다.
- 방문 표시 덕분에 각 정점은 큐(또는 스택)에 한 번만 들어가고 한 번만 꺼내집니다. 여기서
O(V)가 나옵니다. - 정점을 꺼낼 때 그 정점의 이웃 목록을 한 번 훑습니다. 모든 정점의 이웃 목록 길이를 더하면 방향 그래프는
E, 무방향 그래프는 2E입니다. 여기서 O(E)가 나옵니다.
그래서 전체 시간은 O(V + E)입니다. BFS와 DFS는 최선, 평균, 최악이 따로 없고 도달 가능한 부분 전체를 보면 항상 이 비용이 듭니다. 목표 정점을 찾자마자 멈추는 경우에만 더 빨리 끝날 수 있습니다.
인접 행렬을 쓰면 한 정점의 이웃을 찾기 위해 행 전체 V칸을 봐야 하므로 시간이 O(V^2)가 됩니다. 간선이 적은 그래프에서는 큰 차이입니다.
from collections import deque
def bfs_matrix(matrix, start):
n = len(matrix)
dist = [-1] * n
dist[start] = 0
queue = deque([start])
while queue:
u = queue.popleft()
for v in range(n): # 이웃이 아니어도 n칸을 모두 본다
if matrix[u][v] and dist[v] == -1:
dist[v] = dist[u] + 1
queue.append(v)
return dist # 전체 O(V^2)
공간
- 방문 표시, 거리, 부모 배열:
O(V) - BFS 큐: 최악의 경우 한 겹 전체가 들어가므로
O(V) - DFS 스택 또는 재귀 깊이: 최악의 경우 일직선 그래프에서
O(V) - 그래프 자체: 인접 리스트
O(V + E), 인접 행렬 O(V^2)
표현 방식 비교
간선이 정점 수의 제곱에 가까운 조밀한 그래프(예: 정점 1000개, 간선 수십만 개)에서는 행렬도 괜찮은 선택이지만, 실무와 코딩 테스트의 대부분은 희소 그래프라 인접 리스트가 기본입니다. 이웃 여부를 자주 묻는다면 리스트 대신 집합(set)을 이웃 목록으로 써서 평균 O(1) 확인을 얻을 수 있습니다.
격자 그래프
R x C 격자는 정점이 RC개, 정점마다 이웃이 최대 4개이므로 간선도 O(RC)입니다. 격자 BFS는 O(RC) 시간과 공간이 듭니다. 1000 x 1000 격자면 정점 백만 개이므로 Python에서는 리스트 대신 1차원 배열 인덱스(r * C + c)를 쓰는 등 상수 비용을 줄이는 것이 체감됩니다.
다른 알고리즘과의 비교
가중치가 모두 같으면 다익스트라 대신 BFS를 쓰는 것이 더 빠르고 간단합니다.
상수 비용을 키우는 실수
리스트를 큐로 쓰면 pop(0)이 매번 남은 원소를 앞으로 당겨서 BFS가 O(V^2)로 느려집니다.
from collections import deque
import timeit
def drain_list(n):
items = list(range(n))
while items:
items.pop(0) # 매번 O(n)
def drain_deque(n):
items = deque(range(n))
while items:
items.popleft() # 매번 O(1)
n = 100_000
print(timeit.timeit(lambda: drain_list(n), number=1))
print(timeit.timeit(lambda: drain_deque(n), number=1))
재귀 DFS는 Python의 재귀 한도(기본 약 1000)를 넘으면 RecursionError가 납니다. 한도를 올릴 수 있지만 C 스택이 넘치면 프로세스가 죽을 수 있으므로, 깊은 그래프는 반복형으로 바꾸는 것이 안전합니다.
import sys
def depth(n):
return 0 if n == 0 else 1 + depth(n - 1)
print(sys.getrecursionlimit()) # 보통 1000
try:
depth(5000)
except RecursionError:
print("재귀가 너무 깊습니다. 반복형 DFS를 쓰세요.")
정리
인접 리스트 위의 BFS, DFS, 위상 정렬은 모두 O(V + E) 시간에 O(V) 추가 공간을 씁니다. 인접 행렬은 이웃 확인이 빠른 대신 탐색이 O(V^2)가 됩니다. 실제 속도는 deque를 쓰는지, 재귀 깊이를 피했는지 같은 구현 선택에도 크게 좌우됩니다.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.