DFS와 BFS

 이 글은 유데미 컴공선배 파이썬 알고리즘 강의 수강 내용을 정리한 글입니다. 

 

 

 

공통점

 모든 경우의 수를 찾는 완전탐색 방법을 이용한다. 

 

차이점 

탐색 순서의 차이 

 

 DFS ( Depth First Search)

• 깊이 우선 탐색 방법이다. 모든 노드를 탐색하고자 하기 위함이다.
• BFS 보다 간단하다 느리다. 
• 스택(Stack), 재귀를 사용해서 구현한다. 

BFS  (Breadth First Search) 

• 너비우선 탐색 방법이다. 
• 인접한 노드를 먼저 탐색한다 -> 최단 경로를 찾을 때 유리하다. 
• 큐(Queue)로 구현한다.  

 

주로 두 노드 사이에 최단 경로를 찾고 싶을 때 BFS 방법을 선택한다. 지구 상에 존재하는 모든 친구 관계 그래프로 표현한 후 Sam 과 Eden 사이에 존재하는 경로를 찾는 경우  깊이 우선 탐색 DFS의 경우 모든 친구 관계를 살펴봐야할 수도 있으나 너비 우선 탐색 BFS의 경우 Sam 과 가까운 관계부터 찾는다. DFS를 사용하여 모든 경우를 살필 수 있으나 최단 거리 탐색은 보통은 BFS를 쓴다. BFS가 탐색을 할 때 먼저 거리 1로 가볼 수 있는 노드를 다 가보고 없으면 그 다음에 2로 가볼 수 있는 노드, 3으로, 4로 이렇게 넘어가기 때문에 가까이 있는 노드를 먼저 탐색할 수 있다. 

 

 

 

https://algodaily.com/lessons/dfs-vs-bfs 

AlgoDaily - BFS vs. DFS: Understanding Breadth First Search & Depth First Search - Introduction