🔍 BFS vs DFS

모든 정점들을 한 번씩 방문(탐색)함으로써 원하는 자료를 찾는 대표적인 탐색방법들로, 탐색하는 순서만 다를 뿐, 모든 자료를 하나씩 확인해 본다는 점은 같다.

👀 BFS(Breathed First Search)

너비 우선 탐색(BFS)은 하나의 정점을 기준으로 목표하는 정점까지 가는 방법을 탐색할 때, 하나의 정점에서 가장 가까운 정점부터 탐색합니다.
이 때, 가장 먼저 찾아지는 해답이 곧 최단거리이다.

두 정점 사이의 최단 경로 찾을 때 사용하며, 최악의 경우, 모든 경로를 다 살펴보아야 한다.

👀 DFS(Ddepth First Search)

깊이 우선 탐색은 하나의 경로를 끝까지 탐색한 후, 목표한 정점이 도착지점이 아니라면 다음 경로로 넘어가는 탐색 방법이다.

모든 노드를 완전히 탐색하는 것이 가능하지만, DFS와 비교했을 때 상대적으로 탐색 시간이 더 오래걸린다.

🔥 DFS vs BFS

	DFS	BFS
탐색 방법	현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
장점	1. BFS보다 적은 저장공간 필요 2. 찾는 값이 좌측에 있을 수록, 깊은 단계에 있을 수록 유리	1. 최단 경로 보장 2. 노드 수가 적고 깊이가 얕은 값을 찾을 때 유리함
단점	1. 최단 경로 보장x 2. 답이 없는 경로에 깊이 빠질 가능성이 있음	1. 노드의 수가 많을 수록 탐색해야할 노드가 많아짐(비효율적) 2. Queue를 사용하므로 다음에 탐색할 노드들을 저장->노드의 수가 많을 수록 더 큰 저장공간 필요
사용	모든 노드를 방문 하고 싶은 경우	최단 경로를 찾고 싶은 경우
구현 방법	Stack / 재귀	Queue

• 그래프가 굉장히 크다면? => DFS

• 그래프의 규모가 작고, depth가 얕다면? => BFS

Reference: 코드스테이츠