BFS(Breadth-First Search) 알고리즘 구현하기 (자바스크립트)

BFS는 최단 경로를 탐색하기 위해서 많이 사용되는 알고리즘으로, DFS와는 다르게 인접한 노드를 순서대로 방문하지만 각 인접 노드의 자식을 방문하는 건 나중에 이루어진다.

 

자바스크립트로 이를 구현해보면 다음과 같다.

// 그래프의 인접 리스트 표현
const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E']
};

function bfs(graph, startNode) {
  const visited = new Set(); // 방문한 노드를 저장하는 Set
  const queue = [startNode]; // 탐색할 노드를 저장하는 큐

  visited.add(startNode); // 시작 노드 방문 처리

  while (queue.length > 0) {
    const currentNode = queue.shift(); // 큐에서 노드를 하나 꺼냄
    console.log(currentNode); // 현재 노드 출력

    // 현재 노드의 인접 노드를 순회하면서 방문하지 않은 노드를 큐에 추가하고 방문 처리
    for (const neighbor of graph[currentNode]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

bfs(graph, 'A'); // 시작 노드 'A'에서 BFS 탐색 시작

그래프로 표현되는 데이터에서는 위와 같이 queue을 사용하여 bfs를 구현할 수 있다.

먼저 인접한 노드들이 큐에 들어가기 때문에, 인접한 노드를 먼저 순회할 수 있는 알고리즘이다.