DFS와 BFS, 그래프 탐색 알고리즘 비교

그래프와 트리를 탐색하는 방법에서 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)는 가장 많이 사용되는 두 가지 알고리즘.

탐색 방식

DFS (Depth-First Search)
DFS는 가능한 한 깊이 탐색한 후, 더 이상 탐색할 수 없게 되면 마지막 분기점으로 돌아와 다른 경로를 탐색하는 방식.
이 알고리즘은 스택을 사용하여 구현되며, 재귀적으로 호출될 수 있음.
*스택: 후입선출, 가장 최근에 추가된 데이터가 가장 먼저 제거.

// 예시 트리
        A
       / \
      B   C
     / \   \
    D   E   F

DFS를 이용하여 노드를 탐색하면 다음과 같은 순서로 진행

  1. 시작 노드 A에서 B로 이동
  2. B에서 D로 이동
  3. D에서 더 이상 갈 곳이 없으므로 B로 돌아가 E로 이동
  4. E에서 더 이상 갈 곳이 없으므로 A로 돌아가 C로 이동
  5. C에서 F로 이동

탐색 순서는 A → B → D → E → C → F입니다.


BFS (Breadth-First Search)
BFS는 현재 노드의 모든 인접 노드를 탐색한 후, 다음 깊이로 넘어가는 방식.
이 알고리즘은 큐를 사용하여 구현.
*큐: 선입선출, 가장 먼저 추가된 데이터가 가장 먼저 제거.

같은 트리를 BFS로 탐색하면 다음과 같은 순서로 진행

  1. 시작 노드 A에서 인접한 모든 노드(B, C)를 큐에 추가
  2. B와 C를 차례로 탐색
  3. B의 자식 노드(D, E)를 큐에 추가
  4. C의 자식 노드(F)를 큐에 추가

탐색 순서는 A → B → C → D → E → F입니다.


시간 복잡도

두 알고리즘 모두 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점의 수, E는 간선의 수를 나타냄.
따라서 두 알고리즘은 그래프의 크기에 따라 효율적으로 작동.


공간 복잡도

DFS: 최악의 경우 O(h) (h는 트리의 깊이. 재귀 호출 시 스택에 쌓이는 깊이에 따라 다름.
BFS: 최악의 경우 O(w) (w는 트리의 최대 너비). 큐에 쌓이는 노드 수에 따라 다름.

사용 예시

DFS 경로 탐색 문제: 미로 찾기와 같은 문제에서 특정 경로를 찾는 데 유용. 위상 정렬: 작업의 순서를 정하는 데 활용. 연결 요소 탐색: 그래프의 연결된 부분을 찾는 데 사용.

BFS 최단 경로 탐색: 가중치가 없는 그래프에서 최단 경로를 찾는 데 가장 효과적. 레벨 순회: 트리의 각 레벨을 탐색하는 데 사용. 네트워크 흐름 문제: 네트워크의 흐름을 분석하는 데 유용.

참고