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

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

 

정의

루트 노드 (혹은 임의의 다른 노드)에서 시작해서 다음 분기(branch)로

넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

넓게 탐색하기 전에 깊게 탐색하는 것이다.

 

특징

1) 깊이 우선이 너비 우선(BFS)보다 간단하지만 느리다.

2) 자기 자신을 호출하는 순환 알고리즘의 형태를 갖는다.

3) 전위 순회(Pre-Order Traversals) 를 포함한 다른 형태의 순회는 모두 DFS의 한 종류이다.

 

주의점

그래프 탐색의 경우 어떤 노드를 방문했는지 검사해야 무한루프에 빠질 위험이 없다.

 

동작원리

a노드(시작노드) 방문
- 방문을 표시한다

1. a와 인접한 노드들을 차례로 순회
   - 인접한 노드가 없다면 종료
2. a와 이웃된 노드b를 방문했다면, a와 인접한
   다른 노드 방문전 b의 이웃 방문이 우선
   - b를 시작 노드로 DFS 다시 시작
3. b의 분기를 탐색했다면, 다시 a인접 노드 중
   방문안한 노드를 찾는다.
   - b의 분기를 전부 완벽하게 탐색한 뒤
     a의 다른 이웃 노드를 방문 가능

방문이 안된 노드가 없다면 종료,

있다면 다시 그 노드로 돌아가 DFS 시작

 

 

 

시간 복잡도

• DFS는 그래프 (n개의 정점, e개의 간선)의 모든 간선을 조회한다.
  • 인접 리스트로 표현된 그래프 : O(n + e)
  • 인접 행렬로 표현된 그래프 : O(n ^ 2)
• 즉, 그래프 내에 적은 수의 간선만 갖는 희소 그래프(spare graph)의 경우 인접 행렬보다 인접 그래프가 유리하다