DFS 란?

DFS는 이전에 공부했던 BFS와 같은 대표적인 그래프 탐색 방법 중 하나다.
Depth-first, 즉 깊이를 우선으로 탐색하는데
시작 정점부터 차례대로 모든 정점을 한번씩 방문한다.

BFS가 사방으로 퍼져가면서 탐색을 하는 느낌이라면
DFS는 한 가지를 쭉 타고가며 탐색을 하는 느낌이다.

/ WIKIMEDIA COMMONS

위 그림은 그래프에서 DFS가 어떤 방식으로 동작하는 지 보여준다.

• 먼저 시작 노드인 1을 방문한다.
• 1과 인접한 2를 방문한다.
• 2와 인접한 3을 방문한다.
• 3과 인접한 4를 방문한다.
• 4와 인접한 노드가 없으므로 다시 올라가 1과 인접했던 5를 방문한다.
  ...

DFS는 두가지 방법으로 구현할 수 있다.

동작 방식은 다음과 같다.

1. 시작 정점부터 시작해 방문하지 않은 정점이 있으면 방문한다.

2. 1을 반복하며 더 이상 갈 곳이 없는 정점에 도달하면 가장 최근에 방문하지 않고 넘어간 정점까지되돌아가 탐색을 이어간다.

이를 의사코드로 표현해보면
stack

Algorithm dfs(graph, v)
    stack.push(v)
    while (stack)
        v = stack.pop()
        traverse.append(v)
        if (!visited[v])
            visited[v] = true
            stack.push(unvisited adjacent nodes)

재귀함수

Algorithm dfs(graph, v)
    visited[v] = true
    traverse.append(v)
    for (w adjacent to v)
        if (!visited[w])
           dfs(g, w)

트리 자료구조에서 탐색을 하면 방문했던 정점을 다시 방문할 일이 없어 사이클이 발생하지 않지만, 그래프에선 사이클이 발생할 수 있기 때문에 무한 루프에 빠지는 것을 방지하기 위해 방문 표시를 해야한다.