BFS(너비 우선 탐색)

• 인접한 모든 정점들을 방문한 뒤, 더 이상 방문할 정점이 없으면 depth를 내려가고, 다시 인접한 모든 정점들을 방문한다.

• Queue 사용

• 최단 경로 구할 때 사용

• 재귀적으로 동작하지 않는다.

장점/단점

• 장점: 최단 경로를 찾을 수 있다. 답이 되는 경로가 여러 개라도 최단 경로임을 보장한다.

• 단점

  • 최악의 경우에는, 모든 정점들을 다 탐색해야 한다. 실행 시간이 오래 걸린다.
  • 노드의 수가 늘어나면, 탐색해야하는 노드가 많아지기 때문에 비효율적이다.
  • Queue를 통해, 다음에 탐색할 노드를 저장하기 때문에 노드의 수가 많아질수록 큰 저장 공간이 필요하다.

DFS(깊이 우선 탐색)

• 하나의 경로를 끝까지 탐색한 후, 다음 경로로 넘어간다.(최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동)
• 스택 또는 재귀 사용

장점/단점

• 장점

  • 운 좋게 올바른 경로를 선택한다면, 가장 빠른 알고리즘이다.
  • BFS에 비해, 필요한 저장 공간이 적다.
  • 찾으려는 노드가 깊은 단계에 있는 경우, BFS보다 빠르게 찾을 수 있다.

• 단점: 찾은 경로가 최적이 아닐 가능성이 높다. 최악의 경우에는 모든 경로를 탐색해야지 답을 찾을 수도 있고 이는 가장 오랜 시간이 걸린다.

---

시간 복잡도

노드가 N개, 간선이 E개일 때,

인접 리스트: O(N+E)
인접 행렬: O(N²)

행렬은 NxN의 matrix를 돌아야 하기 때문에 O(N²)이다.
리스트는 모든 정점과 모든 간선을 다 거쳤기 때문에 O(N+E)라고 할 수 있다.

활용

1. 모든 정점을 방문 -> BFS/DFS 둘 다 사용 가능

2. 최단 거리 구하기 -> BFS
   DFS로 찾은 첫 번째 경로는 최단 거리가 아닐 수 있기 때문에 BFS를 사용한다.

3. 그래프가 굉장히 크다면(그래프가 깊다면)? -> DFS 사용
   그래프의 규모가 작고(노드의 수가 적고), depth가 얕다면? -> BFS 사용

4. 이동할 때마다 가중치가 붙어서 이동한다거나 이동 과정에서 여러 제약이 있을 경우 -> DFS 사용