DFS (Depth First Search) : 깊이 우선 탐색

DFS, 깊이 우선 탐색이란, 

 

그래프 상에 존재하는 정점에서 인접한 정점 중에 방문하지 않은 정점이 없을 때까지 계속 인접한 다른 임의의 정점으로 이동하며 탐색한다. 인접한 정점 중에 방문하지 않은 정점이 없으면 이전 정점으로 이동한 뒤 다른 정점으로 이동하는 과정을 반복한다.

 

구현 방법은 재귀함수를 이용한 것과, 반복문과 스택을 이용한 것으로 2가지가 있다.

 

수도코드 - 재귀함수로 구현

dfs(int v){

  visited[v] = true;

  for(u in adjacent vertices of v){

    if(!visited[u]){

      dfs(u);

    }

  }

}

인접한 노드를 하나씩 연이어서 계속 방문한다. 그러다가 방문할 노드가 없으면 이전 노드의 인접 노드를 탐색하게 된다.

 

수도코드 - 반복문과 스택으로 구현

dfs(int i){

  stack s;

  s.push(i);

  visited[i] = true;

  while(!s.empty()){

    int v = s.pop();

    for(u in adjacent vertices of v){

      if(!visited[u]){

        s.push(u);

        visited[u] = true;

      }

    }

  }

}

노드를 방문할 때마다 방문하지 않은 주변 노드들이 스택에 들어간다. 가장 마지막에 들어간 노드를 그 다음에 바로 방문하게 되므로 계속 인접한 노드를 하나씩 연이어서 방문하게 되며, 방문할 노드가 없으면 스택에 노드를 새로 넣지 않게 되므로 그 이전에 방문한 노드의 인접 노드들 중 가장 마지막으로 스택에 들어간 노드를 방문하게 된다. 즉, 방문할 노드가 없으면 이전 노드의 인접 노드를 탐색하게 된다.

 

시간 복잡도 : 정점의 개수를 |V|, 간선의 개수를 |E|라고 할 때(무향 그래프일 경우에는 간선 하나당 방향이 서로 다른 유향 간선 2개로 친다), 정점의 방문 횟수와 간선 탐색 수를 primary operation이라고 가정하면 최악의 경우 O(|V| + |E|)