깊이 우선 탐색을 상태로 이해하기: Stack·Visited·DFS Forest

이 글의 시각적 출발점은 Instagram의 DFS 포스트입니다. 원본 캡션·이미지·영상·코드는 복제하지 않았습니다. 본문, TypeScript 예제, cycle과 disconnected graph, 실행 trace, 인터랙티브 보드는 이 글을 위해 독립적으로 다시 설계했으며 기술적 경계는 그래프 라이브러리와 런타임 문서로 교차 확인했습니다.

먼저 결론: DFS는 “깊게 간다”보다 세 상태의 계약이다

깊이 우선 탐색(Depth-First Search, DFS)을 “한 방향으로 끝까지 간 뒤 돌아온다”라고만 기억하면 cycle, 이웃 순서, disconnected graph에서 구현이 쉽게 흔들린다. 실제 알고리즘은 다음 세 상태가 서로 맞물린다.

1. frontier stack: 아직 끝내지 않은 정점과 다음에 검사할 이웃 위치를 보존한다.
2. visited set: 이미 발견한 정점으로 다시 내려가 cycle을 반복하지 않게 한다.
3. visit order 또는 결과 구조: 정점을 처음 발견했을 때 필요한 작업을 정확히 한 번 수행한다.

핵심 불변조건은 다음처럼 쓸 수 있다.

각 active expansion frame은 발견 소유권을 막 얻었거나 이미 visited로 확정된 고유 정점 하나와 아직 검사하지 않은 다음 이웃 위치를 나타낸다. 자식으로 내려가기 전에 visited를 검사하므로 같은 정점의 expansion frame 두 개가 동시에 존재하지 않는다.

재귀 DFS의 함수 호출 stack과 명시적 stack 구현은 이 상태를 서로 다른 장소에 저장할 뿐이다. 이 글의 보드는 두 구현을 같은 graph와 같은 authored neighbor order로 실행해 stack, 현재 edge, visited, 방문 순서를 나란히 보여준다.

입력·출력 계약을 먼저 쓴다

DFS 함수의 입력을 단순히 “그래프”라고 부르면 중요한 선택이 숨는다. 이 글에서는 다음 계약을 사용한다.

• 정점은 고유한 문자열 ID를 가진다.
• 그래프는 adjacency list이며 각 정점의 이웃 배열 순서는 의미 있는 authored order다.
• 존재하지 않는 정점을 가리키는 edge는 입력 검증에서 거부한다.
• directed graph에서는 outgoing edge만 따라간다. undirected graph는 양방향 항목을 모두 넣는다.
• 전체 순회는 graph.nodes 순서로 아직 방문하지 않은 정점을 새 root로 선택한다.
• 출력은 preorder, 즉 정점을 처음 발견한 순간의 배열이다.

따라서 방문 순서는 그래프 자체만의 수학적 속성이 아니다. 시작 정점, root 순서, 각 adjacency 배열의 순서까지 포함한 계약의 결과다. 같은 edge set도 A: [B, C]와 A: [C, B]에서 서로 다른 정상 DFS order를 만들 수 있다.

정점 집합과 adjacency를 별도로 받는 이유도 여기에 있다. adjacency key만 순회하면 outgoing edge가 없는 고립 정점을 빠뜨리거나 객체 key 정렬 규칙에 의존할 수 있다. production API에서는 정점 목록과 이웃 목록을 정규화해 순서를 명시적으로 고정하는 편이 안전하다.

재귀 DFS: 호출 frame이 작업 stack이다

가장 짧은 형태의 재귀 DFS는 다음과 같다.

function visit(node: string) {
  if (visited.has(node)) return
  visited.add(node)
  order.push(node)
  for (const next of graph[node]) {
    if (!visited.has(next)) visit(next)
  }
}

visit(A)가 visit(B)를 호출할 때 런타임 call stack은 A의 loop가 어느 이웃까지 진행됐는지 보존한다. B의 subtree가 끝나면 A frame으로 돌아와 다음 이웃을 계속한다. “되돌아간다”는 표현은 추상적인 동작이 아니라 중단된 for loop의 위치를 frame이 보존한다는 뜻이다.

visited 검사는 반드시 재귀로 더 내려가기 전에 실행한다. A→B→D→B처럼 cycle이 있다면 D frame에서 B가 이미 방문됐음을 확인하고 두 번째 B expansion frame 자체를 만들지 않는다. 함수 entry의 guard도 잘못된 직접 호출에 대비해 방어적으로 유지한다. mark가 recursive call 뒤에 있으면 B와 D가 서로를 계속 호출해 종료하지 않는다.

정점을 방문 순서에 넣는 시점도 계약이다.

• recursive call 전에 기록하면 preorder다.
• 모든 이웃이 끝난 뒤 기록하면 postorder다.
• 진입·종료 시각을 함께 기록하면 edge 분류, cycle 탐지, topological algorithm의 기반을 만들 수 있다.

“DFS order”라는 이름만으로 어느 결과인지 단정하지 말고, discover event인지 finish event인지 API에 적어야 한다.

명시적 stack: 정점만 넣는 것보다 frame을 보존한다

입문 예제는 흔히 정점 ID만 stack에 넣고 pop한 뒤 이웃을 역순 push한다. 작은 그래프에는 충분하지만 recursive DFS와 정확히 같은 authored order를 재현하려면 두 가지를 조심해야 한다.

1. 단순 stack은 여러 이웃을 미리 push하므로 visited를 push 때 표시할지 pop 때 표시할지에 따라 중복 entry와 순서가 달라진다.
2. recursive frame은 현재 정점뿐 아니라 “다음 이웃 index”도 기억한다.

이 글의 명시적 구현은 runtime call stack을 다음 frame으로 직접 모델링한다.

type Frame = { node: string; next: number }

const stack: Frame[] = [{ node: root, next: 0 }]
while (stack.length > 0) {
  const frame = stack.at(-1)!
  const neighbors = graph[frame.node]

  if (frame.next >= neighbors.length) {
    stack.pop()
    continue
  }

  const next = neighbors[frame.next]
  frame.next += 1
  if (visited.has(next)) continue

  visited.add(next)
  order.push(next)
  stack.push({ node: next, next: 0 })
}

이 방식은 재귀 구현과 같은 순서로 한 이웃씩 내려간다. 각 frame은 정점과 loop cursor를 함께 가지므로 reverse-push 규칙에 의존하지 않는다. 큰 입력에서 call stack 한도를 피하면서도 recursive semantics를 보존해야 할 때 유용하다.

visited는 언제 표시해야 하는가

명시적 DFS에는 두 가지 흔한 정책이 있다.

push/discover 시점에 표시

정점을 stack에 넣기 직전에 visited에 추가한다. 같은 정점이 frontier에 여러 번 들어가지 않으므로 stack 크기와 trace가 안정적이다. 이 글의 frame 기반 구현이 이 정책을 사용한다.

pop/process 시점에 표시

pop한 뒤 이미 방문했는지 검사하고 처음일 때만 처리한다. 구현은 짧지만 여러 incoming edge가 같은 정점을 가리키면 같은 정점이 stack에 반복해서 들어갈 수 있다. 결과 정점은 한 번만 처리해도 frontier가 불필요하게 커질 수 있다.

어느 정책이든 정답이 될 수 있지만 “visited”가 discovered를 뜻하는지 processed를 뜻하는지 이름과 metric에서 구분해야 한다. distributed crawler나 비동기 작업 큐로 확장하면 이 차이는 더 커진다. 예약 시점에 원자적으로 소유권을 얻지 못하면 여러 worker가 같은 URL이나 job을 중복 처리할 수 있다.

Cycle에서 종료하는 이유를 불변조건으로 증명한다

유한 그래프에서 정점 수를 V라 하자. 정점은 처음 발견될 때만 visited에 들어가고 이후에는 다시 frame으로 push되지 않는다. 따라서 새 frame을 만드는 횟수는 최대 V다. 각 frame의 이웃 cursor는 뒤로 가지 않고 해당 adjacency list 길이까지만 증가한다.

이로부터 두 사실이 나온다.

1. 정점 발견은 유한 번, 최대 V번이다.
2. edge 검사는 adjacency 항목마다 최대 한 번이므로 유한하다.

그러므로 self-loop, 양방향 edge, 긴 cycle이 있어도 알고리즘은 종료한다. 현재 edge의 도착 정점이 visited라면 “실패”가 아니라 이미 설명된 graph 구조이므로 그 edge만 건너뛴다.

정확성도 같은 상태로 설명할 수 있다.

• soundness: order에 추가되는 정점은 root에서 edge를 따라 도달했거나 outer loop가 선택한 실제 정점이다.
• uniqueness: order 추가 직전에 visited를 확인하고 mark하므로 정점은 최대 한 번 들어간다.
• reachability completeness: 어떤 root에서 도달 가능한 아직 미방문 정점 v가 있다면, root에서 v까지의 첫 미방문 edge가 결국 해당 frame의 cursor에 의해 검사되어 v가 발견된다.

Disconnected graph는 하나의 tree가 아니라 DFS forest다

시작 정점 하나에서 실행한 DFS는 그 정점에서 도달 가능한 component만 순회한다. 전체 그래프를 처리하려면 authored root order를 한 번 더 돈다.

for (const root of graph.nodes) {
  if (!visited.has(root)) visit(root)
}

이미 방문한 root 후보는 이전 component에서 도달한 정점이므로 건너뛴다. 아직 방문하지 않은 정점을 만나면 새 DFS tree가 시작된다. 여러 tree의 집합이 DFS forest다.

undirected graph에서 이렇게 만들어진 root 수는 connected component 수와 같다. directed graph에서는 “weakly connected component 수”라고 단순히 부를 수 없다. outgoing edge로 도달 가능한 관계가 방향에 따라 달라지므로 root 수는 정점 순서와 edge 방향의 영향을 받는다. strong component가 필요하면 DFS 한 번이 아니라 Tarjan이나 Kosaraju처럼 별도의 불변조건을 가진 알고리즘을 사용해야 한다.

시간 O(V+E), 추가 공간 O(V)의 전제

adjacency list에서 전체 forest를 순회하면 각 정점을 한 번 발견하고 각 adjacency entry를 한 번 검사한다. 시간은 O(V+E)다. undirected graph가 edge를 양방향으로 저장하면 각 물리적 edge가 두 entry로 보이지만 2E는 Big-O에서 O(E)다.

추가 공간은 다음을 합쳐 O(V)다.

• visited set 최대 V개
• 결과 order 최대 V개
• 최악 깊이에서 call stack 또는 explicit work stack 최대 V개

이 분석은 adjacency list가 이미 준비되어 있다는 전제다. edge list에서 매 정점마다 outgoing edge 전체를 다시 찾으면 O(VE)까지 악화될 수 있다. dense adjacency matrix에서는 각 정점마다 V칸을 검사하므로 O(V²)다. 자료구조를 말하지 않고 “DFS는 O(V+E)”라고만 말하면 비용 모델이 불완전하다.

재귀 구현의 stack overflow는 복잡도와 별개다

재귀 DFS의 이론적 추가 공간 O(V)가 맞더라도 언어 runtime의 call stack에는 실용적인 깊이 제한이 있다. 긴 chain graph는 cycle이 없어도 호출 깊이가 V가 된다. JavaScript 엔진은 지나치게 깊은 호출에서 RangeError: Maximum call stack size exceeded 또는 유사 오류를 낼 수 있다.

따라서 입력 크기와 최대 깊이가 외부에서 정해지는 서비스라면 다음 중 하나를 선택한다.

• explicit stack으로 전환한다.
• 허용 최대 정점 수·깊이를 입력 계약으로 제한한다.
• generator나 chunked traversal로 작업 예산을 나누고 cancellation을 지원한다.
• 재귀가 충분한 작은 내부 graph라면 근거가 되는 크기 상한을 문서화한다.

tail-call optimization을 기대해 일반 DFS의 안전성을 설명해서는 안 된다. 이웃을 순회하고 돌아와 계속 처리해야 하는 호출은 일반적으로 단순한 tail call이 아니다.

결정적 순서는 테스트와 재현성을 위한 기능이다

Set, Map, database query, filesystem, network response에서 나온 이웃 순서가 우연히 안정적일 것이라고 가정하면 환경 변화가 snapshot, cache key, downstream task order를 흔든다. 순서가 제품 의미를 가진다면 입력에서 보존하고, 의미가 없다면 명시적으로 정렬한다.

다만 정렬 비용은 공짜가 아니다. 각 정점의 degree를 d라고 할 때 이웃 정렬 비용의 합이 추가된다. hot path에서 매번 정렬하기보다 graph ingest 시 정규화하거나, API가 comparator를 받아 필요할 때만 적용하도록 설계할 수 있다.

NetworkX의 DFS preorder 문서도 시작 정점을 주지 않으면 모든 component를 반복해 선택하며, sort_neighbors로 이웃 순서를 제어할 수 있음을 API에 드러낸다. 순서는 구현의 부수 효과가 아니라 호출자가 선택할 수 있는 계약이다.

테스트는 예시 order 하나보다 속성을 검증한다

최소 테스트 행렬은 다음과 같다.

property test로는 결과의 모든 정점이 입력 집합에 있고 중복이 없으며, 전체 forest 모드에서는 결과 집합이 입력 정점 집합과 같은지 확인할 수 있다. recursive와 frame 기반 iterative 구현은 같은 root·neighbor order에서 같은 preorder를 내야 한다. 이 교차 검증은 두 구현이 같은 버그를 공유하지 않는다는 보장은 아니지만 cursor와 visited timing 오류를 찾는 강한 회귀 테스트가 된다.

Production 확장: traversal 결과보다 event와 예산을 설계한다

실서비스 DFS는 배열 하나를 반환하는 데서 끝나지 않는 경우가 많다.

• visitor events: discover vertex, examine edge, finish vertex를 callback이나 generator로 내보낸다.
• parent/depth map: DFS tree edge와 깊이를 기록해 경로나 hierarchy를 복원한다.
• cancellation: AbortSignal과 edge/시간 예산으로 긴 순회를 중단한다.
• mutation policy: 순회 중 graph가 바뀌는 것을 금지하거나 snapshot/version을 고정한다.
• memory budget: visited 전체를 보존할 수 없는 외부 graph라면 정확성·중복 허용·persistent state의 trade-off를 명시한다.
• observability: discovered vertices, examined edges, maximum stack depth, component 수, 중단 이유를 기록한다.

Boost Graph Library의 DFS 문서는 discover/examine/finish 같은 event point와 color map을 분리한다. 이는 DFS를 코드 조각이 아니라 상태 전이와 관찰 hook의 계약으로 보는 좋은 예다. JavaScript의 깊은 재귀 오류는 MDN의 too much recursion 문서에서 runtime failure로 확인할 수 있다.

마지막 원칙

DFS를 구현할 때 “재귀를 쓸까 stack을 쓸까”부터 묻지 않는다. 먼저 정점을 언제 discovered로 소유하는지, frame이 어떤 미완료 작업을 보존하는지, 이웃과 root 순서가 결과에 어떤 약속을 하는지를 쓴다. 그 계약이 정해지면 재귀와 명시적 stack은 같은 상태 기계를 표현하는 두 구현이 된다.