깊이 우선 탐색(DFS, depth-first search)

DFS란?

깊이 우선 탐색은 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다. 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라간다. 이 과정에서 더 이상 갈 곳이 없는 막힌 정점에 도달하면, 마지막에 따라왔던 간선을 따라 뒤로 돌아간다.

예시


  vector<vector<int> > adj; // 그래프의 인접 리스트
  vector<bool> visited; // 각 정점의 방문 여부

  void dfs(int here) { // dfs
    cout << "DFS visits " << here << endl;
    visited[here] = true;

    for(int i = 0; i < adj[here].size(); ++i) { // 인접정점을 순회
      int there = adj[here][i];

      if(!visited[there]) { // 방문한 적 없다면 방문
        dfs(there);
      }
    } // 더 이상 방문할 정점이 없으니, 재귀 호출을 종료하고 이전 정점으로 돌아간다
  }

  void dfsAll() { // 모든 정점을 방문한다
    visited = vector<bool>(adj.size(), false); // visited를 전부 false로 초기화

    for(int i = 0; i < adj.size(); ++i) { // 모든 정점을 순회, 방문한 적 없다면 방문한다
      if(!visited[i])
        dfs(i);
    }
  }

GIF로 확인하는 DFS

01

시간복잡도

어느 그래프 표현 방식을 사용하느냐에 따라 달라진다.

  • 인접 리스트를 사용할 경우
    • 한 정점마다 한 번씩 호출하므로, |V|번 호출한다.
    • 모든 정점에 대해 수행하고 나면 모든 간선을 정확히 한 번(방향 그래프) 혹은 두 번(무향 그래프) 확인한다.
    • 따라서 시간 복잡도는 O(|V| + |E|)가 된다.
  • 인접 행렬을 사용하는 경우
    • 호출 횟수는 그대로 |V|이다.
    • dfs() 내부에서 다른 모든 정점을 순회하며 한 번 실행에 O(|V|)의 시간이 든다.
    • 따라서 시간 복잡도는 O(|V|2)가 된다.

장점

  • 구현이 BFS보다 간단하다.
  • 현재 경로상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적다.
  • 목표 노드가 깊은 단계에 있는 경우 답을 빨리 구할 수 있다.

단점

  • 단순 검색 속도는 BFS보다 느리다.
  • 해가 없는 경우 빠질 가능성이 있다.
  • 구한 해가 최단 경로임을 보장할 수 없다.

Reference