[바미] Search algorithm - Breadth-first search 알고리즘 구현하기.

BFS(Breadth-First Search)?

BFS(Breadth-First Search)는 그래프 자료구조에서 사용되는 탐색 알고리즘 중 하나로, 너비 우선 탐색이라고도 불립니다. 이 알고리즘은 루트 노드에서 시작하여 인접한 모든 노드를 방문한 후에, 그 노드들의 인접한 노드를 차례대로 방문하는 방식으로 탐색을 진행합니다.

 

BFS는 큐(Queue) 자료구조를 사용하여 탐색을 수행합니다. 우선 시작 노드를 큐에 넣고, 큐가 빌 때까지 다음의 과정을 반복합니다.

1. 큐에서 하나의 노드를 꺼냅니다.
2. 해당 노드의 인접한 노드들을 방문합니다.
3. 방문한 노드를 큐에 넣습니다.

이러한 과정을 반복하여, 모든 노드를 방문할 때까지 탐색을 진행합니다.

이렇게 탐색된 노드들의 순서는 노드들의 거리 순서대로 정렬되며, 각 노드들의 최단 거리를 구하는 데에도 사용됩니다.

 

코드 구현

// 그래프 정의
const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E']
};

// BFS 구현
function bfs(graph, startNode) {
  const visited = {}; // 방문한 노드를 저장하는 객체
  const queue = [startNode]; // BFS를 위한 큐
  visited[startNode] = true; // 시작 노드 방문 처리

  while (queue.length > 0) {
    const node = queue.shift(); // 큐에서 하나의 노드를 꺼냄
    const neighbors = graph[node]; // 현재 노드의 이웃 노드들을 가져옴

    console.log(node); // 현재 노드 출력

    for (let i = 0; i < neighbors.length; i++) {
      const neighbor = neighbors[i];
      if (!visited[neighbor]) { // 이웃 노드 중 방문하지 않은 노드가 있다면
        visited[neighbor] = true; // 방문 처리
        queue.push(neighbor); // 큐에 추가
      }
    }
  }
}

// 테스트
bfs(graph, 'A'); // A, B, C, D, E, F 순서대로 출력

코드 설명

• graph: 그래프를 나타내는 인접 리스트.
• start: 시작 노드.
• queue: BFS를 수행할 때 사용하는 큐.
• visited: 방문한 노드를 저장하는 Set.

실행 순서는 아래와 같습니다.

1. queue에 start 노드를 추가합니다.
2. visited Set에 start 노드를 추가합니다.
3. queue가 빌 때까지 다음을 반복합니다.
   • queue에서 노드를 하나 꺼냅니다.
   • 꺼낸 노드를 출력합니다.
   • 꺼낸 노드의 인접 노드를 찾습니다.
   • 인접 노드 중에서 visited Set에 없는 노드를 찾아서 visited Set에 추가하고 queue에 추가합니다.

위 코드에서 visited Set은 방문한 노드를 저장합니다. 이는 중복 방문을 방지하기 위함입니다. queue는 BFS를 수행할 때 사용하는 큐입니다. BFS에서는 먼저 방문한 노드는 먼저 처리되어야 하기 때문에, 큐를 이용해 먼저 들어온 노드를 먼저 처리합니다.