본문으로 건너뛰기
실습하기

너비 우선 탐색(BFS)이란?

너비 우선 탐색은 그래프 또는 트리를 탐색할 때, 한 노드에서 시작하여 레벨별로 인접한 노드를 먼저 탐색하는 알고리즘입니다.


키워드​

  • 큐(Queue): BFS는 큐를 사용하여 방문할 노드들을 관리합니다.

  • 레벨별 탐색: BFS는 각 노드의 레벨별로 인접한 노드를 탐색합니다.

  • 최단 경로: BFS는 시작 노드에서 목표 노드까지의 최단 경로를 찾는 데 자주 사용됩니다.

  • 시간 복잡도: (O(|V| + |E|)), 여기서 (|V|)는 정점의 수, (|E|)는 간선의 수입니다.


BFS의 단계별 과정​

  1. 노드 선택: 탐색을 시작할 노드를 선택합니다.

  2. 방문 및 탐색: 선택한 노드를 방문하고, 인접한 노드를 큐에 추가합니다.

  3. 레벨별 탐색: 큐에서 노드를 꺼내 방문하고, 그 인접 노드들을 큐에 추가합니다.

  4. 탐색 완료: 큐가 비어있을 때 탐색을 종료합니다.


BFS의 특징​

  • 너비 우선: 각 레벨의 노드를 탐색한 후 다음 레벨의 노드로 넘어갑니다.

  • 단층 탐색(Layered Search): 노드를 레벨별로 탐색하여 레벨이 동일한 노드들을 먼저 방문합니다.

  • 최단 경로 탐색: BFS는 무방향 그래프에서 시작 노드에서 목표 노드까지의 최단 경로를 찾는 데 효과적입니다.

  • 탐색 순서: 노드의 탐색 순서는 큐의 구현 방식과 시작 노드에 따라 달라집니다.


BFS의 장단점​

  • 장점: 최단 경로를 찾는데 효과적이고, 모든 레벨의 노드를 방문합니다. 너비 우선 탐색은 순환 경로가 있는 그래프에서도 잘 작동합니다.

  • 단점: BFS는 DFS에 비해 메모리 사용량이 많을 수 있습니다. 모든 인접 노드를 저장해야 하기 때문에 큰 그래프에서는 메모리 부담이 클 수 있습니다.

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!