위 이미지는 BFS와 DFS를 나타낸 그림이다.

헷갈리지 말아야 할 것이 있다.
이 두가지 알고리즘이 반드시 트리구조의 그래프에만 적용되는 것이 아니라 모든 그래프에 적용 될 수 있다는 점이다.
다만 이해를 돕기 위해 트리 형태로 된 그래프를 가져왔다.

BFS (Breathed First Search)

BFS는 너비우선탐색 알고리즘이다.

위 그림에서 알 수 있듯

• 시작 정점을 방문 한 후
  
  
• 시작 정점에 인접한 모든 정점들을 우선 방문한다.
  
  
• 더 이상 방문 할 정점이 없으면 한 depth 내려가서
  
  
• 다시 인접한 모든 정점들을 우선 방문한다.

DFS (Ddepth First Search)

DFS는 깊이우선탐색 알고리즘이다.

위 그림에서 알 수 있듯

• 시작 정점을 방문 한 후
  
  
• 자식을 모두 탐색한다.
  
  
• 이때 연결된 노드가 존재하지 않을 때까지 들어왔다면
  
  
• 한 단계 이전으로 돌아가 다시 알고리즘을 수행한다.

---

장점 / 단점

BFS

장점:

1. 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 뽀장
2. 최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있다.
3. 노드 수가 적고 깊이가 얕은 해가 존재 할 때 유리하다.

단점:

1. 재귀호출을 사용하는 DFS와 달리 큐를 이용해 다음에 탐색 할 노드들을 저장하기 때문에 노드의 수가 많을 수록 필요없는 노드들까지 저장해야 하기 때문에 더 큰 저장공간 필요.
2. 노드의 수가 늘어나면 탐색해야하는 노드가 많아지기 때문에 비효율적

DFS

장점:

1. BFS에 비해 저장공간의 필요성이 적다. 백트래킹을 해야하는 노드들만 저장해주면 된다.
2. 찾아야하는 노드가 깊은 단계에 있을 수록, 그 노드가 좌측에 있을 수록 BFS보다 유리하다.

단점:

1. 답이 아닌 경로가 매우 깊다면, 그 경로에 깊이 빠질 우려가 있다.
2. 찾은 해가 최단 경로라는 보장이 없다.