javascript - BFS(Breadth-First Search)

BFS(Breadth-First Search)

그래프 탐색 알고리즘 중 하나로, 너비 우선 탐색이라고도 합니다. 이 알고리즘은 그래프를 너비 방향으로 탐색하여 시작 노드에서부터 레벨별로 탐색을 진행합니다. BFS는 시작 노드에서부터 가까운 이웃 노드부터 순차적으로 방문하며, 레벨별로 탐색하면서 최단 경로를 찾는 데 유용합니다.

BFS의 동작 방식은 다음과 같습니다:

시작 노드를 방문하고, 방문한 노드를 큐(Queue)에 추가합니다.
큐에서 노드를 하나씩 꺼내어 방문하고, 해당 노드의 모든 이웃 노드를 큐에 추가합니다.
큐가 빌 때까지 위 과정을 반복합니다.
BFS는 레벨 단위로 탐색하기 때문에, 같은 레벨에 있는 노드들을 모두 탐색한 후에 다음 레벨로 넘어갑니다. 이로 인해 시작 노드로부터의 최단 경로를 먼저 찾아낼 수 있습니다.

다음은 인접 리스트 형태의 그래프를 기준으로 BFS를 적용하는 예시입니다.

const graph = {
  1: [2, 3],
  2: [4],
  3: [5],
  4: [],
  5: []
};

const visited = {};

function bfs(startNode) {
  const queue = [];
  queue.push(startNode);
  visited[startNode] = true;

  while (queue.length > 0) {
    const currentNode = queue.shift();
    console.log('방문한 노드:', currentNode);

    for (const neighbor of graph[currentNode]) {
      if (!visited[neighbor]) {
        queue.push(neighbor);
        visited[neighbor] = true;
      }
    }
  }
}

bfs(1);

이 예제에서는 시작 노드를 1로 설정하고 BFS를 실행합니다. 큐를 사용하여 방문할 노드를 관리하며, 노드를 방문하면 해당 노드의 이웃 노드를 큐에 추가합니다. 이러한 방식으로 레벨 단위로 탐색을 진행하면서 그래프의 모든 노드를 방문하게 됩니다.

BFS의 구현 방식은 언어나 상황에 따라 다를 수 있지만, 핵심적인 아이디어는 노드를 너비 우선으로 탐색하는 것입니다.