DFS와 BFS 차이: 탐색 순서·최단 경로와 Python 예제

DFS는 한 경로를 깊게 따라간 뒤 되돌아오고, BFS는 시작점에서 가까운 정점부터 층별로 탐색합니다. DFS는 스택·재귀, BFS는 큐를 주로 사용합니다. BFS는 간선 비용이 모두 같을 때 간선 수 기준 최단 경로를 구할 수 있습니다.

차이와 선택 기준

비교	DFS	BFS
자료구조	스택 또는 재귀 호출 스택	큐
대표 질문	연결되어 있는가, 어떤 경로로 도달하는가	최소 몇 단계로 도달하는가
최단 경로	일반적으로 보장하지 않음	비가중치·동일 비용 간선에서 보장
인접 리스트의 전체 탐색 시간	O(V+E)	O(V+E)

같은 그래프의 탐색 순서

다음은 Python 3에서 실행할 수 있는 예제입니다. 4에서 1로 돌아가는 간선이 있어 방문 집합이 없으면 반복할 수 있습니다. 정점 5는 시작점 1과 연결되지 않았습니다.

from collections import deque

graph = {1: [2, 3], 2: [4], 3: [4], 4: [1], 5: []}

def dfs(node, seen=None):
    if seen is None:
        seen = set()
    seen.add(node)
    order = [node]
    for neighbor in graph.get(node, []):
        if neighbor not in seen:
            order.extend(dfs(neighbor, seen))
    return order

def bfs(start):
    queue = deque([start])
    parent = {start: None}
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in parent:
                parent[neighbor] = node
                queue.append(neighbor)
    return order, parent

def path_to(parent, target):
    if target not in parent:
        return None
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]

order, parent = bfs(1)
assert dfs(1) == [1, 2, 4, 3]
assert order == [1, 2, 3, 4]
assert path_to(parent, 4) == [1, 2, 4]
assert path_to(parent, 5) is None

왜 큐에 넣을 때 방문 처리하나요?

위 BFS는 parent에 기록하는 순간 방문 처리합니다. 2와 3이 모두 4를 가리켜도 4는 한 번만 큐에 들어갑니다. 꺼낼 때까지 처리를 미루면 같은 정점이 여러 번 들어갈 수 있습니다. parent는 방문 확인과 경로 복원을 함께 담당합니다.

같은 거리의 경로가 여럿이면 인접 정점의 저장 순서에 따라 선택되는 경로가 달라질 수 있습니다. BFS가 항상 유일한 경로를 반환하는 것은 아닙니다.

복잡도와 구현의 한계

O(V+E)는 인접 리스트로 각 정점과 간선을 상수 번 확인하는 탐색의 기준입니다. 인접 행렬에서 모든 이웃 후보를 확인하면 O(V²)이 될 수 있습니다. 위 재귀 DFS는 설명용이며 리스트를 합치는 비용과 Python 재귀 깊이 제한도 있습니다. 큰 그래프는 명시적 스택과 하나의 결과 리스트를 사용하는 구현을 검토하세요. 가중치가 다른 그래프의 최단 경로에는 BFS를 그대로 적용하지 않습니다.