아주 간단한게만 말하자면, 그래프 중에서 방향성이 있는 비순환 그래프
주로 두 노드 사이의 ⭐️최단 경로⭐️를 찾을 때 사용한다.
🧐 A와 B사이의 거리를 구해야 한다. 두 가지 방식으로 했을 때의 차이?
그렇지 않을까?
DFS는 하나의 정점에서 계속 파고든다. 가까운 한명에서 계속 파고들어서 아니면 다시 돌아가!! 이런 개념
BFS는 나랑 연결된 애들은 일단 다 본다. 없으면 걔네랑 또 연결된 애들 본다!
그러니 최단 경로라는 문제에서 DFS는 최적해를 보장 못하는 게 맞다!
N=노드, E=간선 일 때,
일반적으로 간선(E)의 크기가 N^2에 비해 상대적으로 적기에 인접 리스트 방식이 효율적이다.
1) 그래프의 모든 정점을 방문하는 것이 주요한 문제
단순 모든 정점 방문이라면 DFS, BFS 어느 것을 사용해도 상관없다.
2) 경로의 특징을 저장해둬야 하는 문제
각 정점에 숫자가 적혀있고 a~b까지 가는 경로를 구하는 데, 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다. (BFS는 경로의 특징을 갖지 못한다)
3) 최단 거리를 구해야 하는 문제
미로 찾기 등, 최단 거리 일때는 BFS가 유리하다.
DFS의 경우, 처음 발견되는 답이 최단 거리가 아닐 수도 있지만 BFS는 너비 우선으로 찾기때문에 최단 거리를 여러개 받아서 Math.min()으로 비교해서 구해줄 수 있따.
+) 검색 대상 그래프가 정말 크다면 DFS
+) 검색 대상 규모가 크지 않고, 검색 시작 시점으로부터 원하는 대상이 별로 멀지 않다면 BFS