BFS & DFS

너비 우선 탐색 (BFS)

그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘

BFS의 특징

• Queue를 이용하여 구현할 수 있다.
• 시작 지점에서 가까운 정점부터 탐색한다.
• V가 정점의 수, E가 간선의 수일 때 BFS의 시간복잡도는 O(V+E)다.

출처: 이선협 강사님 데브코스 강의자료

깊이 우선 탐색 (DFS)

그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘

DFS의 특징

• Stack을 이용하여 구현할 수 있다.
• 시작 정점에서 깊은 것부터 찾는다.
• V가 정점의 수, E가 간선의 수일 때 DFS의 시간복잡도는 O(V+E)다. BFS와 시간 복잡도는 동일하다.
  출처: 이선협 강사님 데브코스 강의자료

---

😅 해당 내용은 공부하면서 정리한 글입니다. 틀린 부분이나 오해하고 있는 부분이 있다면 피드백 부탁드립니다.