그래프 DFS: 방문 표시로 순환을 멈추고 연결을 따라가기

깊이 우선 탐색은 한 이웃의 탐색을 끝낸 뒤 다음 이웃으로 이동합니다. 정점에 들어가자마자 방문 표시를 해야 순환과 중복 간선이 있어도 각 정점을 한 번만 처리할 수 있습니다.

선수 지식: 배열·반복문·함수 호출·재귀의 종료 조건

• 정점과 인접 목록으로 그래프를 표현하기
• visited를 기록하는 시점을 설명하기
• 방문 순서와 연결되지 않은 정점 구분하기

인접 목록은 다음에 갈 수 있는 정점을 저장합니다

그래프는 정점과 정점을 잇는 간선으로 관계를 표현합니다. 이 글에서는 정점을 0부터 V−1까지의 정수로 정하고, graph[u]에 u에서 바로 갈 수 있는 정점 번호를 넣습니다. 예를 들어 [[1,2],[0,2],[0,1],[]]에는 정점 네 개가 있습니다. 0·1·2는 서로 연결되어 있고 3의 인접 목록은 비어 있습니다. 배열의 위치가 정점의 식별자이므로 화면에 표시할 이름이 같더라도 방문 여부가 섞이지 않습니다.

간선의 방향도 입력에 포함된 약속입니다. 무방향 간선 0—1을 표현하려면 0의 목록에 1을, 1의 목록에 0을 모두 넣어야 합니다. 한쪽에만 적으면 코드가 자동으로 반대 방향을 만들어 주지 않습니다. 목록에서 이웃을 어떤 순서로 적었는지는 DFS의 출력 순서를 바꾸지만, 시작점에서 도달 가능한 정점의 집합을 바꾸지는 않습니다. 따라서 순서를 비교할 때에는 이웃 나열 순서까지 함께 확인해야 합니다.

들어갈 때 표시하고 돌아오면 다음 이웃을 봅니다

탐색 함수가 정점 u에 들어오면 visited[u]를 먼저 참으로 바꾸고 결과에 u를 추가합니다. 그다음 인접 목록을 읽으며 아직 방문하지 않은 이웃만 재귀 호출합니다. “현재 호출이 시작된 정점은 이미 방문 처리되어 있다”는 상태를 모든 호출이 지키는 것이 핵심입니다. 호출이 끝날 때까지 표시를 미루면 0→1→0처럼 되돌아오는 간선에서 같은 정점이 다시 호출될 수 있습니다.

복귀는 정점을 방문하지 않았던 상태로 되돌리는 동작이 아닙니다. 이 예제는 도달 가능성을 구하므로 한 번 처리한 정점의 방문 표시는 끝까지 유지합니다. 모든 단순 경로를 열거하는 백트래킹과 혼동하여 복귀할 때 표시를 지우면 같은 부분 그래프를 거듭 처리하게 됩니다.

한 번의 DFS가 그래프 전체를 방문하지는 않습니다

시작 정점이 0이면 결과는 [0,1,2]이고, 고립된 3은 결과에 없습니다. 정점 3을 따로 시작점으로 주면 결과는 [3]입니다. 빈 인접 목록도 유효한 정점이며, 간선이 없어도 시작점 자체는 방문합니다. 모든 연결 구역을 구하려면 바깥 반복문에서 정점을 하나씩 확인하고, 아직 방문하지 않은 정점마다 같은 방문 배열을 공유하는 탐색을 시작해야 합니다. 방향 그래프에서 이런 방문 묶음을 무방향 연결 요소나 강한 연결 요소라고 곧바로 부를 수는 없습니다.

자기 자신으로 향하는 간선이나 같은 이웃이 두 번 적힌 경우에도 방문 표시가 재호출을 막습니다. 다만 반복된 간선 항목을 읽는 비용까지 없어지는 것은 아닙니다. 정점 수 V와 인접 목록 항목 수 E를 기준으로 비용을 세어야 합니다. 이 예제는 탐색 전에 입력 전체의 번호 범위도 확인하므로, 시작점에서 닿지 않는 목록까지 포함하여 O(V+E) 시간이 듭니다.

호출 스택과 입력 경계를 함께 확인합니다

방문 배열과 결과 배열은 각각 O(V) 공간을 사용합니다. 정점이 일렬로 이어진 그래프에서는 재귀 호출도 V단계까지 깊어질 수 있습니다. 이 재귀 예제는 작은 그래프의 원리를 확인하는 데 적합합니다. 큰 입력에서는 실행 환경의 호출 스택 한도를 고려해 명시적인 스택을 사용하세요. 반복형에서도 재귀와 정확히 같은 순서를 원한다면 이웃을 넣는 순서와 방문 처리 시점을 설계해야 합니다.

빈 그래프에는 유효한 시작 정점이 없으므로 이 함수는 오류를 냅니다. 범위를 벗어난 이웃 번호도 조용히 무시하지 않고 먼저 거절합니다. 마지막으로 출력 순서가 다르다는 이유만으로 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 dfs(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;
}

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

node algorithm-graph-dfs-visited.mjs

[0,1,2]
[3]

비용과 적용 범위

정점 V개, 인접 목록 항목 E개일 때 입력 검사를 포함한 시간 O(V+E), 추가 공간 O(V)입니다. 재귀 깊이는 최악 O(V)이며 큰 그래프는 호출 스택 한도를 고려해야 합니다.

직접 확인해 보기

graph=[[1,2],[0],[0],[]]에서 dfs(graph,0)의 결과는 무엇이며, 정점 3은 왜 빠질까요?

함께 읽을 글

• JavaScript 그래프 구현: 인접 리스트·인접 행렬 비교와 BFS — 인접 리스트와 행렬의 표현 차이를 복습합니다.
• 그래프 연습: 연결 구역 크기를 작은 순서로 출력하기 — 방문 배열을 여러 탐색에서 공유하여 연결 구역을 세는 연습으로 이어집니다.

참고 자료

• Competitive Programmer’s Handbook — 12.1 Depth-first search — 깊이 우선 탐색의 방문 상태와 인접 리스트 기반 선형 탐색 원리.