DFS와 BFS 비교: 깊이·대기열·최소 간선 수를 구분하기

DFS는 진행 중인 가지를 끝까지 따라가고, BFS는 시작점에서 같은 간선 수만큼 떨어진 정점을 먼저 처리합니다. 모든 간선의 비용이 같을 때 최소 간선 수는 BFS의 거리로 구할 수 있습니다.

선수 지식: 그래프 인접 리스트·DFS 방문 표시·스택과 큐

• 같은 입력의 DFS·BFS 순서 비교하기
• BFS의 거리와 부모 배열 읽기
• 가중치가 있는 최단 경로와 구분하기

다음 정점을 보관하는 방식이 순서를 만듭니다

두 탐색은 모두 시작점에서 도달 가능한 정점을 찾지만, 아직 처리하지 않은 후보를 다루는 순서가 다릅니다. 재귀 DFS는 마지막으로 시작한 호출의 이웃을 먼저 처리합니다. BFS는 먼저 발견한 정점을 큐 뒤에 넣고 큐 앞에서 하나씩 꺼냅니다. DFS에는 현재 가지가, BFS에는 다음 차례를 기다리는 정점들이 남습니다. 방문 배열의 의미는 같더라도 어떤 후보를 먼저 꺼내느냐가 결과의 모양을 바꿉니다.

예제의 방향 간선은 0→1, 0→2, 1→3, 3→4, 2→4입니다. 5는 고립 정점입니다. 0의 이웃을 1, 2 순서로 적으면 DFS는 0→1→3→4를 먼저 진행한 뒤 2를 방문하므로 [0,1,3,4,2]가 나옵니다. BFS는 0 다음에 1과 2를 처리하므로 [0,1,2,3,4]입니다. 탐색 순서만 보고 정점 4까지의 최단 경로를 결정해서는 안 됩니다.

BFS는 거리 한 층씩 넓어집니다

시작점의 거리를 0으로 두고 u에서 처음 발견한 v에는 distance[v]=distance[u]+1을 기록합니다. 큐에는 거리 d인 정점들이 거리 d+1인 정점보다 먼저 들어갑니다. 따라서 처음 발견한 거리가 최소 간선 수입니다. 예제에서 DFS가 먼저 도착한 4의 경로는 0→1→3→4로 세 간선이지만, BFS는 0→2→4의 두 간선을 발견합니다. DFS의 방문 깊이를 최단 거리라고 저장하면 이 차이를 놓칩니다.

부모 배열은 처음 발견한 간선의 출발점을 저장합니다. 4에서 부모 2, 다시 부모 0을 따라간 뒤 순서를 뒤집으면 경로를 복원할 수 있습니다. 최소 경로가 여러 개라면 인접 목록의 순서에 따라 부모가 달라질 수 있지만 최소 거리는 같습니다.

큐에서 꺼낼 때보다 발견할 때 표시합니다

BFS 예제는 별도의 참·거짓 배열 대신 distance[v]===-1을 미발견 상태로 사용합니다. 큐에 넣기 전에 거리와 부모를 설정하므로 같은 정점이 여러 이웃에게서 다시 발견되어도 한 번만 들어갑니다. 표시를 꺼내는 순간까지 미루면 여러 정점이 같은 목적지를 동시에 큐에 넣을 수 있습니다. 중복 간선이나 순환이 있는 그래프에서 불필요한 작업이 늘어나는 흔한 원인입니다.

배열을 큐로 쓸 때에는 앞 원소를 매번 지우는 대신 head 인덱스를 증가시킵니다. 이미 처리한 자리는 건너뛰고, 새 정점은 뒤에 추가합니다. 이 방식은 배열 앞부분을 반복해서 이동시키지 않습니다. 도달할 수 없는 5의 거리는 끝까지 −1이고 부모도 −1입니다. 시작점의 부모 역시 −1이지만 거리가 0이므로 두 상태를 구분할 수 있습니다. 부모 값만으로 도달 여부를 판단하지 마세요.

문제에서 필요한 결과로 탐색을 고릅니다

단순한 도달 여부와 연결 구역 탐색에는 두 방식 모두 사용할 수 있습니다. 재귀적인 가지의 진행과 복귀가 필요하면 DFS가 자연스럽고, 모든 간선의 비용이 같은 그래프에서 최소 이동 횟수가 필요하면 BFS가 자연스럽습니다. 간선마다 비용이 다르면 적은 간선 수가 싼 경로를 뜻하지 않습니다. 음수가 없는 가중치에는 다익스트라처럼 비용을 기준으로 처리하는 다른 알고리즘이 필요합니다.

인접 리스트에서는 두 탐색의 시간 규모가 O(V+E)입니다. 이 예제는 전체 입력 검증을 포함하므로 도달하지 못한 정점의 목록도 확인합니다. BFS의 큐·거리·부모, DFS의 방문·결과와 호출 스택은 최악 O(V) 공간을 사용합니다. 어느 방식이 항상 메모리를 적게 쓴다고 단정할 수 없습니다. 긴 사슬에서는 DFS 호출이 깊어지고, 너비가 큰 그래프에서는 BFS 대기열이 커집니다. 예제 DFS는 작은 입력용 재귀 구현이므로 큰 입력에서는 호출 스택 한도를 확인해야 합니다.

전체 코드와 직접 실행

개념을 읽었다면 아래 예제를 직접 실행하며 상태 변화를 확인할 수 있습니다.

function validateGraph(graph, start) {
  if (!Array.isArray(graph)) throw new TypeError('인접 목록 배열이 필요합니다.');
  if (!Number.isInteger(start) || start < 0 || start >= graph.length) {
    throw new RangeError('시작 정점이 범위를 벗어났습니다.');
  }
  for (const neighbors of graph) {
    if (!Array.isArray(neighbors)) throw new TypeError('정점마다 인접 배열이 필요합니다.');
    for (const v of neighbors) {
      if (!Number.isInteger(v) || v < 0 || v >= graph.length) {
        throw new RangeError('인접 정점이 범위를 벗어났습니다.');
      }
    }
  }
}

function dfsOrder(graph, start) {
  validateGraph(graph, start);
  const visited = Array(graph.length).fill(false);
  const order = [];
  function visit(u) {
    visited[u] = true;
    order.push(u);
    for (const v of graph[u]) if (!visited[v]) visit(v);
  }
  visit(start);
  return order;
}

function bfs(graph, start) {
  validateGraph(graph, start);
  const distance = Array(graph.length).fill(-1);
  const parent = Array(graph.length).fill(-1);
  const queue = [start];
  distance[start] = 0;
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head];
    for (const v of graph[u]) {
      if (distance[v] !== -1) continue;
      distance[v] = distance[u] + 1;
      parent[v] = u;
      queue.push(v);
    }
  }
  return { order: queue, distance, parent };
}

const graph = [[1,2],[3],[4],[4],[],[]];
console.log(JSON.stringify(dfsOrder(graph,0)));
console.log(JSON.stringify(bfs(graph,0)));

node algorithm-dfs-bfs-comparison.mjs

[0,1,3,4,2]
{"order":[0,1,2,3,4],"distance":[0,1,1,2,2,-1],"parent":[-1,0,0,1,2,-1]}

비용과 적용 범위

인접 리스트의 정점 V개, 항목 E개 기준으로 입력 검증을 포함한 DFS·BFS 시간은 각각 O(V+E), 추가 공간은 O(V)입니다. BFS 거리의 최단성은 모든 간선의 비용이 같다는 조건에 적용됩니다.

직접 확인해 보기

0→1, 0→2, 1→3, 3→4, 2→4에서 4의 BFS 거리와 부모는 무엇일까요? 간선 0→2의 비용만 100으로 바뀌어도 최소 비용이라고 할 수 있을까요?

함께 읽을 글

• JavaScript 그래프 구현: 인접 리스트·인접 행렬 비교와 BFS — BFS를 구성하는 그래프 표현과 기본 구현을 먼저 확인합니다.
• 큐와 FIFO: head 인덱스로 JavaScript 대기열 만들기 — 배열 앞을 지우지 않고 FIFO 순서를 지키는 head 인덱스를 복습합니다.
• 자료구조 스택 쉽게 이해하기: push pop으로 문제 풀이 감 잡기 — DFS 호출의 진행·복귀를 LIFO 관점에서 이해합니다.

참고 자료

• Competitive Programmer’s Handbook — 12.1–12.2 Graph traversal — DFS의 가지 탐색, BFS의 층별 탐색과 무가중치 최단 거리 조건.