DFS와 BFS

• 그래프 탐색과 관련된 알고리즘의 종류

Sample

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

• 내부적으로 스택을 사용한다.
  • 1
  • 1 → 2
  • 1 → 2 → 3
  • 1 → 2 → 3 → 4
  • 1 → 2 → 3 → 4 → 5
  • 1 → 2 → 3 → 4 → 5 → 6
  • 1 → 2 → 3 → 4 → 5 → 6 → 7
• 시작점에서 시작하여 막다른 점이 나올 때까지 탐색한다.
• 막다른 점을 발견하면 되돌아 갈 길을 역추적(backtracking)하는 과정을 거친다.

BFS(너비 우선 탐색, Breadth First Search)

• 내부적으로 큐를 사용한다.
  • 1
  • 1 → 2
  • 1 → 2 → 7
  • 1 → 2 → 7 → 8
  • 1 → 2 → 7 → 8 → 3
  • 1 → 2 → 7 → 8 → 3 → 6
  • 1 → 2 → 7 → 8 → 3 → 6 → 9
  • 1 → 2 → 7 → 8 → 3 → 6 → 9 → 12
• 시작점을 기준으로 가장 가까운 정점(level 순)을 탐색한다.

DFS, BFS 탐색 방법

• 인접리스트, 인접행렬을 이용하여 문제를 풀 수 있다.
• 방문하지 않은 정점(노드)은 -1 혹은 0으로 표기하고 방문할 경우 1로 변경하여 탐색할 정점을 선택한다.

DFS, BFS 시간복잡도

- DFS 인접리스트: $O(V+E)$

- DFS 인접행렬: $O(V^2)$

DFS, BFS 특징 비교

• 메모리 사용 ⇒ DFS < BFS
  • 현재 레벨의 정점에 대해서 기억하고 있어야 함
• 트리의 제일 아래쪽을 찾아야할 때에는 DFS, 중간 단계에 목적지를 찾아야 한다면 BFS가 빠르니 상황에 따라 판단하라