인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.

깊이우선순회 (DFS)

1. 출발점 s에서 시작한다.

2. 현재 노드를 visited로 mark하고 인접한 노드들 중 unvisited 노드가 존재하면 그 노드로 간다.

3. 2번을 계속 반복한다.

4. 만약 unvisited인 노드가 존재하지 않는 동안 계속해서 직전 노드로 되돌아간다.

5. 다시 2번을 반복한다.

6. 시작노드 s로 돌아오고 더 이상 갈 곳이 없으면 종료한다.

다른 예)

DFS 깊이우선탐색

DFS (G, V)  
  visited[v] <- YES;
  for each node adjacent to u do
    if visited[u] = NO then
      DFS(G, u);
  end.
end.  

• 그래프가 disconnected이거나 혹은 방향 그래프라면 DFS에 의해서 모든 노드가 방문되지 않을 수도 있음

• DFS를 반복하여 모든 노드 방문

  DFS-ALL(G)
  {
    for each v ∈ V
      visited[V] <- NO;
    for each V ∈ V
      if ( visited[V] = NO ) then
        DFS(G, V);
  }
  

  시간복잡도: O(n+m)