BFS(Breadth-First Search), 깊이 우선 탐색, JavaScript

 

BFS, 너비 우선 탐색

BFS(너비 우선 탐색, Breadth-First Search)은 그래프 혹은 트리에서 한 노드(정점)로부터 시작하여 가까운(직접 연결된) 노드부터 차례대로 방문하는 알고리즘입니다. 즉, 루트 노드(시작 노드)에 인접한 노드들을 먼저 모두 탐색한 뒤, 그다음 레벨의 노드들을 방문하는 방식입니다.

출처 : https://developer-mac.tistory.com/64

 

특징

• 큐(Queue)를 사용 : 먼저 들어온 노드를 먼저 처리하는 FIFO 구조.
• 계층(Level) 기반 탐색 : 시작 노드로부터 거리가 같은 노드들을 먼저 모두 방문.
• 방문 기록(Visited) 필요 : 무한 루프 방지 및 중복 탐색 방지를 위해 방문 여부를 저장.
• 시간 복잡도 O(V + E) : V는 노드 수, E는 간선 수이며, 모든 노드와 간선을 한 번씩만 확인.

 

활용 분야

• 가중치가 없는 그래프에서 최단 경로 탐색:
  • 예) 미로 문제나 네트워크에서 최소 단계로 목표 지점에 도달하는 경우
• 트리의 레벨 순회(Level Order Traversal):
  • 예) 이진 트리(BST)에서 각 레벨별 노드를 순회
• 연결 요소(Component) 확인:
  • 예) 소셜 네트워크에서 특정 노드와 연결된 모든 노드를 찾을 때
• 네트워크, 퍼즐 등 상태 전이(State Transition) 문제:
  • 예) 퍼즐 해법 탐색, 오염 전파 시뮬레이션

 

---

BFS 구현

구현 시 주의 사항:

• `visited` 자료구조에 방문 기록을 저장하여 중복 방문 방지
• `queue`를 활용해 순서를 관리하며 너비 우선으로 노드를 방문
• 그래프 표현 방식(인접 리스트/인접 행렬 등)은 자유롭게 변경 가능

// 그래프를 객체 형태(인접 리스트)로 표현
const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [],
  E: ['F'],
  F: []
};

// BFS 구현 함수
function bfs(graph, start) {
  const visited = new Set();  // 방문 기록
  const queue = [];           // 탐색 대기열

  // 시작 노드를 큐에 넣고 방문 처리
  queue.push(start);
  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift(); 
    console.log(node);  // 방문할 때마다 실행할 작업

    // 인접 노드 검사
    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

// A 노드부터 탐색
bfs(graph, 'A');
// 실행 결과 예: A → B → C → D → E → F

 

 

 

Reference

• 1 [나를위한노트] | [코딩테스트 대비] DFS, BFS 정리