BFS

BFS ?

• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 시작 노드로부터 가까운 노드들부터 먼저 탐색하는 알고리즘이다.
• 무방향 그래프나 가중치가 동일한 그래프에서 최단 경로를 보장하지 때문에, 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
• 그래프나 트리의 모든 정점을 특정 레벨 순서로 탐색할 때 적합하다 !

💡 BFS 핵심 개념 - 방문 여부 체크

• DFS와 동일하게 방문 여부를 체크해야 한다.

💡 DFS 핵심 개념 - 그래프 구현 방법에 따라 달라지는 시간 복잡도

노드의 수 = V, 간선의 수 = E

1. 인접 리스트를 이용한 방법 - O(V + E)

• 모든 노드 방문 - O(V) → BFS는 모든 노드를 한 번씩 방문하기 때문에 O(V) 시간 복잡도가 요구된다.