깊이 우선 탐색(DFS) 알고리즘

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

깊이 우선 탐색의 중요한 특성은 더 따라갈 간선이 없을 경우 이전으로 돌아간다는 점입니다. 이것을 구현하기 위해서는 지금까지 거쳐온 정점들을 모두 저장해 둬야 하는데, 재귀 호출을 이용하면 이와 같은 일을 간단하게 할 수 있습니다. 재귀 호출한 함수가 종료하면 호출한 위치로 다시 돌아가기 때문이지요.

  // 그래프의 인접 리스트 표현
  vector<vector<int> > adj;
  // 각 정점을 방문했는지 여부를 나타낸다.
  vector<bool> visited;

  void dfs(int here) {
    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를 모두 false로 초기화한다.
    visited = vector<bool>(adj.size(), false);
    // 모든 정점을 순회하면서 아직 방문한 적 없으면 방문한다.
    for (int i = 0; i < adj.size(); ++i)
      if (!visited[i])
        dfs(i);
  }

dfs()는 아직 방문하지 않은 정점으로 이어지는 간선을 만날 경우 재귀 호출을 통해 해당 정점을 방문합니다. 더이상 갈 정점이 없을 경우 이전으로 돌아간다는 요구 조건이 자연스럽게 구현된 것을 볼 수 있지요.

한 가지 유의할 점은 모든 정점에 대해 순서대로 dfs()를 호출하는 dfsAll() 함수의 존재입니다. 그래프에서는 모든 정점들이 간선을 통해 연결되어 있다는 보장이 없기 때문에, dfs()만으로는 모든 정점을 순서대로 발견한다는 목적에 부합하지 않습니다. 예를 들어, 서로 연결되지 않은 두 개의 부분으로 나누어진 그래프의 경우, dfs()로는 두 개의 조각 중 한쪽밖에 발견할 수 없습니다. 대개 깊이 우선 탐색은 그래프 전체의 구조를 파악하기 위해 사용되므로, 그래프의 구조상 한 번에 모든 정점을 다 볼 수 없는 경우에도 모든 정점을 다 방문할 필요가 있습니다.

시간복잡도

인접 리스트를 사용해 그래프를 표현하는 경우, dfs()는 한 정점마다 한 번씩 호출되므로, 정확히 |V|번 호출됩니다. dfs() 한 번의 수행 시간은 모든 인접 간선을 검사하는 for문에 의해 지배되는데, 모든 정점에 대해 dfs()를 수행하고 나면 모든 간선을 정확히 한 번(방향 그래프의 경우) 혹은 두 번(무향 그래프의 경우) 확인함을 알 수 있지요. 따라서 깊이 우선 탐색의 시간 복잡도는 O(|V|+|E|)가 됩니다.