**너비 우선 탐색 (BFS, Breadth-First Search)**은 가중치가 동일한 그래프에서 노드를 탐색하는 방법 중 하나입니다. BFS는 루트 노드에서 시작하여 인접한 노드를 우선적으로 탐색하는 방식으로 동작합니다.

사용 사례

• 최단 경로를 찾거나 그래프의 모든 노드를 탐색해야 할 때 사용됩니다.
• 두 노드 사이의 최단 경로, 네트워크의 홉 수, 노드 간의 거리 등을 계산하는 데에 활용될 수 있습니다.

시간 복잡도

• BFS의 시간 복잡도는 그래프에 있는 노드의 수를 V, 간선의 수를 E라고 할 때 **O(V + E)**입니다.
• 각 노드를 한 번 방문하고, 각 간선을 한 번씩 탐색하기 때문입니다.

특징

• 큐를 사용하여 구현할 수 있습니다.
• 모든 간선의 가중치가 동일한 무방향 그래프에서 최단 경로를 찾는 문제에 매우 유용하다.
  • 다익스트라 알고리즘과 BFS 알고리즘 둘 다 그래프에서의 최단 거리를 찾는 문제에 유용하다는 공통점이 있지만. 다익스트라 알고리즘은 가중치가 있는 그래프에서 BFS 알고리즘은 가중치가 없는 그래프에서 사용할 수 있다는 차이점이 있다.
• 레벨 순서대로 노드를 방문하기 때문에, 레벨 단위로 탐색할 수 있는 특징이 있습니다.
  • 레벨이란 가중치가 동일한 그래프에서 루트 노드로 부터 노드간 이동 횟수를 의미한다.

장점

• 최단 경로를 보장합니다. BFS는 너비를 우선으로 탐색하므로, 시작 노드로부터 가까운 노드부터 탐색하기 때문에 최단 경로를 보장합니다.
• 무방향 그래프에서도 최적의 솔루션을 찾을 수 있습니다. BFS는 모든 노드를 동일한 레벨로 탐색하므로, 무방향 그래프에서 최적의 솔루션을 찾을 수 있습니다.