BFS (Breadthed First Search) 너비우선 탐색 이란?

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

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
• 즉, 깊게(deep) 탐색하기 전에 넓게(wide)탐색하는 것이다.
• 너비 우선탐색 (BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다.

너비 우선 탐색(BFS)의 장단점

• 장점 : 최선의 경우, 가장 빠른 알고리즘이다. '운 좋게' 항상 결과에 도달하는 올바른 경로를 선택한다면, 깊이 우선탐색이 최소 실행시간에 결과를 도출한다
• 단점 : 찾은 경로가 최적이 아닐 가능성이 있다. 최악의 경우, 가능한 모든 경로를 탐험하고서야 결과를 찾으므로, 결과에 도달하는데 가장 오랜 시간이 걸릴수도있다.

DFS (Depth First Search) 깊이 우선 탐색이란?

루트 노드(혹은 다른 임의의 노드)에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는방법

• 미로를 탐색할때 오른손으로 벽을 짚고 미로를 탐색하는 방법과 유사하다
• 즉, 넓게(wide)탐색하기 전에 깊게(deep) 탐색하는 것이다.
• 모든 노드를 방문 하고자 할때 이방법을 사용할수있다.
• 단순 검색 속도 자체는 BFS에 비해서 느리다.

깊이 우선 탐색(DFS)의 장단점

• 장점 : 최적의 경로를 찾을수있다.
• 단점 : 런타임이 오래걸린다.

그래프가 굉장히 크다면 BFS 👍
반대로, 그래프의 규모가 작고, depth가 얕다면 DFS 👍