너비 우선 탐색(BFS) & 깊이 우선 탐색(DFS)

그래프 탐색 방법 2가지

1. 너비 우선 탐색

2. 깊이 우선 탐색

 

 

너비 우선 탐색(Breadth First Search)

 

탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘

큐(Queue) 사용 , 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

 

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

출처 https://developer-mac.tistory.com/64

 

 

 

 

 

 

 

깊이 우선 탐색 (Depth First Search)

 

최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

스택(Stack) 사용

 

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다른 분기로 넘어가기 전에

해당 분기를 완벽하게 탐색하는 방식

 

 

 

 

출처 https://developer-mac.tistory.com/64

 

 

DFS와 BFS의 차이

 

 

[그림 출처 : https://namu.wiki/w/BFS]