그래프 탐색 설계: DFS와 BFS 선택 기준
그래프의 정점·간선 모델과 인접 리스트·행렬 표현을 정리하고, DFS와 BFS의 탐색 방식·복잡도·운영 선택 기준을 다룬다.
2026-08-15 · 최초 발행 2024-04-29
관계를 모델링하는 그래프의 기본 단위
그래프는 정점 집합 V와 정점 사이의 연결을 나타내는 간선 집합 E로 구성하며, G = (V, E)로 표기한다. 네트워크, 상태 전이, 의존성처럼 개체 사이의 관계 자체가 핵심인 문제를 표현할 때 쓰인다.
간선의 성격에 따라 무방향 그래프와 방향 그래프로 나뉜다. 무방향 그래프는 양방향 연결을, 방향 그래프는 유향 간선을 나타낸다. 비용이나 거리 같은 값이 간선에 붙으면 가중치 그래프가 되고, 그렇지 않으면 무가중치 그래프가 된다.
정점은 개체·상태·노드를 나타내며 속성을 가질 수 있다. 간선은 관계나 전이를 표현하고, 방향·가중치·용량 같은 메타데이터를 포함할 수 있다. 그래프를 다루기 전에는 방향성, 연결 여부, 가중치 존재 여부를 구분해야 한다.
그래프 저장 방식은 데이터 밀도와 필요한 연산을 기준으로 정한다. 희소 그래프에는 공간 복잡도가 O(V+E)인 인접 리스트가 유리하다. 반대로 간선 존재 여부를 O(1)에 확인해야 하는 밀집 그래프라면 공간 O(V^2)를 사용하는 인접 행렬이 맞을 수 있다. 간선 목록도 별도의 표현 방식으로 사용할 수 있다.
연결 요소, 강연결과 약연결은 네트워크 구조를 해석하는 기준이 된다. 또한 사이클의 존재 여부는 위상 정렬 가능 여부를 결정한다.
DFS와 BFS가 푸는 문제는 다르다
깊이우선탐색(DFS)은 한 경로를 가능한 깊게 따라간 뒤 되돌아오는 방식이다. 경로와 사이클 탐색, 위상 정렬, 연결 요소 분해에 적합하다. 방문 여부를 기록하고 재귀 호출이나 명시적 스택으로 인접 정점을 탐색한다. 방문 순서와 도달 가능성을 얻을 수 있으며, 필요하면 부모 정보나 발견·완료 시간도 남긴다. 이 시간 정보는 간선 분류에 활용할 수 있고, DFS는 Kosaraju/Tarjan을 이용한 강연결 요소 분석의 기반이 된다.
사이클을 분석하거나 의존성의 순환을 찾아야 할 때는 DFS를 적용한다. DAG의 빌드·배포 순서는 DFS 기반 위상 정렬로 결정할 수 있으며, 탐색 중 사이클을 발견하면 빌드를 중단하고 해당 경로를 보고할 수 있다. 연결성을 확인하거나 브리지와 아티큘레이션 포인트를 찾기 전에도 DFS가 전처리 역할을 한다.
DFS의 시간 복잡도는 O(V+E), 공간 복잡도는 재귀 스택을 포함해 O(V)다. 재귀 깊이에 비례해 공간을 사용하며 프레임 상수가 작아 메모리 효율적일 수 있다. 비연결 그래프라면 미방문 정점마다 탐색을 반복해야 한다. 재귀 제한과 스택 오버플로가 우려되는 환경에서는 명시적 스택을 쓰는 반복 구현이 적합하다. 자기 루프나 다중 간선은 방문 검사로 중복 처리를 막는다.
너비우선탐색(BFS)은 시작점 가까이의 정점부터 레벨 순서로 넓혀 간다. 큐가 프런티어를 관리하며, 무가중치 그래프 또는 동일 가중치 그래프에서는 최단 경로를 보장한다. 최소 간선 수 경로와 레벨별 탐색에 적합하고, 탐색 결과로 레벨별 트리도 얻을 수 있다. 시작 정점을 큐에 넣고, 꺼낸 정점의 미방문 이웃을 방문 처리한 뒤 부모를 기록해 다시 큐에 넣는다.
무가중치 네트워크에서 최소 홉 경로를 구할 때는 BFS를 적용한다. 네트워크와 라우팅의 홉 수 기준 최단 경로나 장애 우회 탐색, 타일 기반의 무가중 맵에서 최단 이동 경로를 찾는 경우가 이에 해당한다. 간선에 가중치가 있으면 BFS 대신 Dijkstra 또는 Bellman-Ford가 필요하며, 가중치 그래프의 최단 경로가 요구되면 Dijkstra/A*로 대체한다.
BFS 역시 시간 복잡도는 O(V+E), 공간 복잡도는 O(V)다. 부모 맵을 남기면 경로를 복원할 수 있다. 비연결 그래프에서는 모든 정점에 대해 BFS를 반복하고, 대규모 그래프에서는 스트리밍이나 외부 메모리 큐를 고려한다.
| 관점 | DFS | BFS |
|---|---|---|
| 시간·공간 | O(V+E) / O(V), 재귀·스택 비용 |
O(V+E) / O(V), 큐 비용 |
| 메모리 양상 | 경로 깊이에 비례, 최악 O(V) 스택·재귀 |
프런티어 크기에 비례, 최악 O(V) 큐 |
| 확장성 | 깊은 그래프에서 재귀 위험, 반복 구현 필요 | 넓은 그래프에서 큐가 커져 메모리 요구 증가 |
| 병렬성 | 컴포넌트 수준 병렬화 가능, 경로 의존성 큼 | 레벨 단위 병렬 확장에 유리 |
| 탐색 순서 | 인접 리스트 순서에 따라 경로가 달라짐 | 인접 순서가 같으면 레벨별 결정적 순서 |
| 안정성 | 스택 오버플로 가능, 조정 필요 | 메모리 압박에 취약하나 안정적 실행 용이 |
| 활용 특성 | 위상 정렬·사이클 탐지에 유리 | 경로 길이·거리 계산과 디버깅이 직관적 |
방문 상태와 자료구조로 탐색을 제어한다
BFS와 DFS 모두 visited 집합으로 재방문을 막아 무한 루프를 예방한다. 인접 정점의 나열 순서도 실제 방문 순서에 영향을 준다. 재현 가능한 탐색 순서가 필요하면 인접 리스트를 정렬하거나 고정된 순서를 유지한다.
얕고 넓은 그래프에서는 BFS의 프런티어가 커져 메모리 사용량이 급증할 수 있다. 이 경우 DFS가 프런티어를 축소해 메모리 사용량을 최대 30~60% 절감할 수 있으며, 이 효과는 그래프 구조에 의존한다. 메모리 피크가 핵심 제약이면 반복형 DFS를 우선 검토하고, 병렬 처리나 레벨 분석이 필요하면 BFS를 우선한다. 대규모 그래프에서 BFS를 운영할 때는 큐 길이 상한 알림을 두고 메모리 피크를 관찰할 필요가 있다.
깊은 그래프에서는 DFS의 재귀 스택 오버플로가 운영상 제약이 된다. 시스템 스택 제한이 낮거나 최대 재귀 깊이가 우려되는 환경에서는 재귀 DFS 대신 반복형 스택 구현을 표준으로 삼는 편이 안전하다. 검색과 크롤링에서 깊이 제한과 확장 제어가 필요하면 BFS의 레벨별 큐를 쓰고, 도메인 내부를 깊게 조사하며 방문 범위를 줄여야 할 때는 스택 기반 DFS를 적용한다.
경로 탐색과 의존성 분석
추천이나 전파 범위를 계산하거나 레벨 기반 접근 제한을 구현할 때는 BFS의 경로 존재성 및 거리 정보가 활용된다. BFS는 감염 확산 단계 시뮬레이션과 레벨별 대응 시나리오 설계에도 사용된다.
퍼즐이나 백트래킹 탐색에서는 DFS로 해 경로의 존재 여부를 빠르게 확인할 수 있다. 그래프 분석과 보안 영역에서는 DFS가 타잔/코사라주 기반의 SCC·커뮤니티 탐지에 활용된다.
탐색 복잡도 O(V+E)는 큰 그래프에서도 선형 시간 탐색을 가능하게 한다. 밀도 1% 그래프에서는 인접 리스트의 메모리 사용량이 인접 행렬 대비 약 1/100 수준이다. 표준 탐색 패턴을 재사용하면 구현과 디버깅이 단순해지고, 입력 검증, visited 관리, 부모·레벨·시간 정보 수집은 탐색 구현의 표준 절차로 남겨야 한다.
Python으로 구현하는 DFS·BFS
전제조건
- Python 3.10+, 표준 라이브러리만 사용
- 그래프: 인접 리스트(dict[str, list[str]] 또는 list[list[int]])
# Python 3.10+
from collections import deque
from typing import Dict, List, Tuple, Optional
Graph = Dict[str, List[str]]
def dfs(graph: Graph, start: str) -> List[str]:
visited = set()
order = []
stack = [start]
while stack:
v = stack.pop()
if v in visited:
continue
visited.add(v)
order.append(v)
# 인접 정점 순서 역정렬 시 전통적 DFS와 유사한 결과
for nei in reversed(graph.get(v, [])):
if nei not in visited:
stack.append(nei)
return order
def bfs(graph: Graph, start: str) -> Tuple[List[str], Dict[str, Optional[str]]]:
visited = set()
parent: Dict[str, Optional[str]] = {start: None}
order = []
q = deque([start])
while q:
v = q.popleft()
if v in visited:
continue
visited.add(v)
order.append(v)
for nei in graph.get(v, []):
if nei not in visited and nei not in parent:
parent[nei] = v
q.append(nei)
return order, parent
def reconstruct_path(parent: Dict[str, Optional[str]], target: str) -> List[str]:
if target not in parent:
return []
path = []
cur = target
while cur is not None:
path.append(cur)
cur = parent[cur]
return list(reversed(path))
if __name__ == "__main__":
g: Graph = {
"A": ["B", "C"],
"B": ["D", "E"],
"C": ["F"],
"D": [],
"E": ["F"],
"F": []
}
print("DFS:", dfs(g, "A")) # 예: ['A', 'B', 'D', 'E', 'F', 'C']
order, parent = bfs(g, "A")
print("BFS:", order) # 예: ['A', 'B', 'C', 'D', 'E', 'F']
print("path A->F:", reconstruct_path(parent, "F")) # 예: ['A', 'B', 'E', 'F']반복형 DFS는 시작 정점을 스택에 넣고, 스택에서 꺼낸 정점이 아직 방문되지 않았을 때만 방문 처리한다. 인접 정점을 역순으로 스택에 넣으면 인접 리스트의 낮은 인덱스부터 방문하는 순서를 유지할 수 있다. 부모 포인터를 함께 기록하면 DFS에서도 경로 추적에 필요한 정보를 남길 수 있다.
# Python 3.10+
from collections import deque
def bfs(graph: dict, start):
if start not in graph:
raise ValueError("start not in graph")
visited, order = set(), []
parent, level = {start: None}, {start: 0}
q = deque([start])
while q:
v = q.popleft()
if v in visited:
continue
visited.add(v)
order.append(v)
for u in graph.get(v, []):
if u not in visited and u not in parent:
parent[u] = v
level[u] = level[v] + 1
q.append(u)
return order, parent, level
def dfs_iter(graph: dict, start):
if start not in graph:
raise ValueError("start not in graph")
visited, order = set(), []
parent = {start: None}
stack = [start]
while stack:
v = stack.pop()
if v in visited:
continue
visited.add(v)
order.append(v)
# 인접 역순 push 시, 낮은 인덱스부터 방문
for u in reversed(graph.get(v, [])):
if u not in visited:
if u not in parent:
parent[u] = v
stack.append(u)
return order, parent
if __name__ == "__main__":
G = {
"A": ["B", "C"],
"B": ["D", "E"],
"C": ["F"],
"D": [],
"E": ["F"],
"F": []
}
b_order, b_parent, b_level = bfs(G, "A")
d_order, d_parent = dfs_iter(G, "A")
print("BFS:", b_order, b_level)
print("DFS:", d_order)