DFS(Depth-First Search)와 BFS(Breath-First Search)

거대한 그래프에서 특정 조건을 만족하는 노드를 찾는 가장 효율적인 방법은 무엇일까? 본 포스팅에서는 그래프의 노드를 탐색 혹은 방문하는 유명한 알고리즘인 DFS(Depth-First Search)와 BFS(Breadth-First Search)에 대해 소개하고자 한다.

 

DFS(Depth-First Search)

DFS는 그래프의 한 경로를 끝까지 탐색한 후, 다른 경로를 탐색하는 방법이다. 깊이를 우선으로 탐색하는 방식이다. DFS는 아래와 같은 특징을 가진다.

• 구현 방식: 재귀나 스택 자료구조를 사용하여 구현한다.
• 완전 탐색: 한 경로의 끝까지 가고, 더 이상 진행할 수 없으면 이전 노드로 돌아와 다른 경로를 탐색한다.
• 메모리 사용량: 경로의 깊이에 비례하여 메모리를 사용한다.

예를 들어, 아래와 같은 완전 이진 트리 형태의 그래프를 노드 1부터 탐색한다고 하자. 

이때 DFS는 아래와 같은 순서로 탐색한다.

1 | 2 | 4 (backtrack to 2) | 5 (backtrack to 1) | 3 | 6 (backtrack to 3) | 7

 

노드 4처럼 더 이상 탐색할 수 없는 leaf node에 도달하면 부모로 올라가서 탐색을 계속하고, 탐색을 완료했다면 다시 부모로 올라가는 방식이다.

---

BFS(Breath-First Search)

BFS는 너비를 우선하여 탐색하는 방법으로, 그래프의 모든 노드들을 같은 깊이에서 먼저 탐색한 후, 다음 깊이의 노드들을 탐색하는 방법이다. BFS는 아래와 같은 특징을 가진다.

• 구현 방식: 주로 큐 자료구조를 사용하여 구현한다.
• 최단 경로 탐색: 각 노드를 최단 경로로 탐색할 때 유용하다.
• 메모리 사용량: 너비에 비례하여 메모리를 사용한다.

위에 나왔던 완전 이진 트리를 BFS로 노드 1부터 탐색하는 순서는 아래와 같다.

(level 1: 1, 2, 3) | (level 2: 2, 4, 5) | (level 3: 3, 6, 7)

 

같은 깊이로 묶여 있는 노드들을 한 번에 탐색하고, 해당 깊이의 탐색이 완료되면 다음 깊이로 넘어가는 형태임을 확인할 수 있다.

---

 

DFS와 BFS는 구현하고자 하는 프로그램에 따라 적절한 것을 선택하여 사용하면 된다. DFS와 BFS는 각각 주로 아래와 같은 종류의 문제에 사용된다.

 

• DFS: 경로 탐색, 백트래킹 문제 (예: 미로 찾기), 모든 가능한 경로 탐색
• BFS: 최단 경로 탐색, 레벨별 탐색 (예: 사회적 네트워크에서 특정 단계까지의 모든 친구 찾기)