DFS / BFS

DFS (Depth-First Search)

 

DFS란 깊이 우선 탐색으로 그래프를 탐색하는 방법의 하나이다.

 

 

위의 그림과 같이 최대한 깊이 내려간 뒤, 더 이상 내려갈 곳이 없을 경우 옆 노드로 이동하여 탐색하는 방법이다.

 

DFS의 특징

• Stack의 자료구조
• 재귀 함수를 이용하여 구현
• 그래프의 깊이가 깊을수록 빠름

---

BFS (Breadth-First Search)

 

BFS란 넓이 우선 탐색으로 그래프를 탐색하는 방법의 하나이다.

 

 

위 그림과 같이 최대한 인접 노드를 탐색한 후 더 이상 갈 수 없을 때 하위 노드를 탐색하는 방법이다.

 

BFS의 특징

• Queue 자료 구조
• Queue를 이용하여 구현
• 찾는 노드가 인접할 때 유리
• 노드가 많을수록 메모리 소비가 큼