DFS와 BFS 그래프 탐색 구현: 스택·큐와 경로 복원

탐색 순서는 스택과 큐에서 갈린다

그래프 탐색은 정점(Vertex)과 간선(Edge)으로 이뤄진 관계 구조에서 경로, 연결성, 최단 거리를 찾는 기본 절차다. 방향 그래프인지, 가중치가 있는지에 따라 표현과 적용 방식은 달라지지만, 시작 정점에서 도달 가능한 정점을 중복 없이 방문한다는 점은 같다.

DFS(Depth-First Search)는 한 방향으로 가능한 깊게 진행한 뒤 되돌아온다. BFS(Breadth-First Search)는 시작점에서 가까운 레벨부터 차례로 넓혀 간다. 이 차이는 각각 스택과 큐를 사용한다는 구조에서 비롯된다.

그래프는 보통 인접 리스트 또는 인접 행렬로 표현한다. 인접 리스트는 O(V+E) 공간을 사용해 희소 그래프에 적합하고, 인접 행렬은 O(V^2) 공간을 사용하지만 간선 존재 여부를 확인하거나 밀집 그래프를 다룰 때 유리하다.

방문 집합은 어느 탐색이든 빠질 수 없다. Set 또는 Boolean 배열로 이미 방문한 정점을 기록하면 중복 방문을 막을 수 있고, 평균 O(1)로 확인할 수 있다. 탐색은 스택이나 큐가 비었을 때 끝나며, 목표 정점을 찾는 작업이라면 그 시점에 조기 종료할 수도 있다.

큐를 따라 진행하는 너비 우선 탐색

BFS에서는 시작 정점을 큐에 넣고 방문 처리한 뒤, 큐 앞에서 정점을 꺼내 인접 정점을 확인한다. 아직 방문하지 않은 정점은 부모를 기록하고 큐 뒤에 추가한다. 부모 맵은 탐색 순서뿐 아니라 경로를 되짚는 데도 사용된다.

⤢✕

DFS는 재귀 호출로 작성할 수 있지만, 깊이가 큰 그래프에서는 명시적인 스택을 쓰는 반복형이 적합하다. BFS는 큐에서 앞쪽 원소를 꺼내야 하므로 대용량 처리에서는 양끝 연산을 O(1)로 보장하는 deque를 사용한다.

스택과 큐를 코드로 구현하기

Python 3.10+ 환경에서 인접 리스트를 딕셔너리와 리스트로 구성할 수 있다. 다음 스택과 큐 구현은 빈 자료구조에서 꺼내는 경우 IndexError를 발생시킨다.

from collections import deque

class Stack:
    def __init__(self): self._s = []
    def push(self, x): self._s.append(x)
    def pop(self):
        if not self._s: raise IndexError("pop from empty stack")
        return self._s.pop()
    def empty(self): return not self._s

class Queue:
    def __init__(self): self._q = deque()
    def enqueue(self, x): self._q.append(x)
    def dequeue(self):
        if not self._q: raise IndexError("dequeue from empty queue")
        return self._q.popleft()
    def empty(self): return not self._q

재귀형과 반복형으로 DFS 작성하기

그래프 클래스는 방향 여부를 보관하고, 간선을 추가할 때 무방향 그래프라면 반대편 인접 목록도 함께 갱신한다. 방향 그래프에서는 이 반대편 추가를 하면 안 되며, 탐색 알고리즘의 나머지 로직은 동일하다.

반복형 DFS는 스택에서 꺼낸 뒤 방문 여부를 검사한다. 재귀형과 비슷한 순서가 필요하다면 인접 정점을 역순으로 스택에 넣는다.

from collections import deque
from typing import Any, Dict, List, Set, Tuple, Optional

class Graph:
    def __init__(self, directed: bool = False):
        self.adj: Dict[Any, List[Any]] = {}
        self.directed = directed

    def add_edge(self, u: Any, v: Any):
        self.adj.setdefault(u, []).append(v)
        self.adj.setdefault(v, [])
        if not self.directed:
            self.adj[v].append(u)

    def neighbors(self, u: Any) -> List[Any]:
        return self.adj.get(u, [])

def dfs_recursive(g: Graph, start: Any) -> List[Any]:
    if start not in g.adj: raise KeyError("start not in graph")
    visited: Set[Any] = set()
    order: List[Any] = []

    def _dfs(u: Any):
        visited.add(u)
        order.append(u)
        for v in g.neighbors(u):
            if v not in visited:
                _dfs(v)
    _dfs(start)
    return order

def dfs_iterative(g: Graph, start: Any) -> List[Any]:
    if start not in g.adj: raise KeyError("start not in graph")
    visited: Set[Any] = set()
    order: List[Any] = []
    stack: List[Any] = [start]

    while stack:
        u = stack.pop()
        if u in visited:
            continue
        visited.add(u)
        order.append(u)
        # 재귀와 유사한 순서를 원하면 역순으로 push
        for v in reversed(g.neighbors(u)):
            if v not in visited:
                stack.append(v)
    return order

BFS의 부모 맵으로 최단 경로 되짚기

비가중치 그래프에서 BFS는 최단 경로를 보장한다. 정점을 처음 큐에 넣을 때 부모를 기록하면, 목표 정점에서 시작점까지 부모를 역순으로 따라가 경로를 복원할 수 있다. 탐색 범위 밖의 정점은 부모 맵에 없으므로 빈 경로를 반환한다.

from collections import deque
from typing import Dict, Any, List, Optional, Tuple

def bfs(g: Graph, start: Any) -> Tuple[List[Any], Dict[Any, Optional[Any]]]:
    if start not in g.adj: raise KeyError("start not in graph")
    visited = {start}
    q = deque([start])
    parent: Dict[Any, Optional[Any]] = {start: None}
    order: List[Any] = []

    while q:
        u = q.popleft()
        order.append(u)
        for v in g.neighbors(u):
            if v not in visited:
                visited.add(v)
                parent[v] = u
                q.append(v)
    return order, parent

def reconstruct_path(parent: Dict[Any, Optional[Any]], target: Any) -> List[Any]:
    if target not in parent:
        return []
    path: List[Any] = []
    cur: Optional[Any] = target
    while cur is not None:
        path.append(cur)
        cur = parent[cur]
    path.reverse()
    return path

# 사용 예시
if __name__ == "__main__":
    g = Graph(directed=False)
    edges = [(1,2),(1,3),(2,4),(3,4),(4,5)]
    for u,v in edges: g.add_edge(u,v)

    print("DFS(rec):", dfs_recursive(g, 1))
    print("DFS(iter):", dfs_iterative(g, 1))
    order, parent = bfs(g, 1)
    print("BFS:", order, "path to 5:", reconstruct_path(parent, 5))

같은 복잡도라도 선택 기준은 다르다

항목	DFS	BFS
성능(시간)	O(V+E), 조기 목표 발견 불확실	O(V+E), 비가중치 최단 경로 조기 확보
확장성(메모리 패턴)	깊이 편향, 최대 깊이만큼 스택 사용	폭 확장, 레벨별 큐 크기 증가 가능
일관성(탐색 순서)	인접 순서/스택 처리에 민감	레벨 순서로 예측 가능성 높음
안정성	재귀 시 스택 오버플로 위험	큐 기반, 재귀 위험 없음
운영 편의	구현 단순, 사이클 탐지 용이	경로 복원(parent)로 운영 가독성 높음

두 알고리즘 모두 시간과 공간 복잡도는 O(V+E)다. 방문 집합과 부모 맵은 O(V), 인접 리스트는 O(V+E)를 사용한다.

목표가 비가중치 최단 경로라면 BFS와 부모 맵이 자연스럽다. 사이클 탐지, 위상 정렬, 연결 요소 분해에는 DFS가 맞는다. 네트워크나 웹 크롤링에서는 BFS로 크롤링 폭을 제어하면서 레이트 리밋과 큐 백프레셔를 적용할 수 있다. 퍼즐과 상태공간 탐색에서는 DFS로 해를 찾고, BFS로 최단 단계의 해를 구할 수 있다.

테스트 재현성을 확보하려면 인접 리스트를 정렬하거나 안정적인 삽입 순서를 유지해야 한다. 시작 정점이 그래프에 없을 때는 KeyError를, 빈 스택·큐 연산에는 IndexError를 처리하도록 입력 검증을 앞에 둔다.

희소 그래프(예: V=10^6, E≈3V)에서는 인접 리스트가 O(V+E) 메모리로 행렬 대비 약 수백 배 절감된다. 비가중치 경로 문제에서는 Dijkstra 대신 BFS를 적용해 상수 시간과 구현 비용을 줄일 수 있다. 자료구조와 방문·부모 맵의 역할을 분리해 두면 코드 가독성과 유지보수성이 좋아지고, 디버깅과 운영 장애 대응도 수월해진다.