BFS 너비 우선 탐색

BFS

BFS

• 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조를 이용하며, 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 큐에 삽입하고 방문처리한다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

• 최단 거리 구하기에서 많이 사용

BFS 구현

1. 시작 노드인 1을 큐에 삽입하고 방문처리

2. 큐에서 노드 1을 꺼내 방문하지 않은 인접 노드 2, 3, 8을 큐에 삽입하고 방문 처리

3. 큐에서 노드 2를 꺼내 방문하지 않은 인접 노드 7을 큐에 삽입하고 방문처리

4. 큐에서 노드 3을 꺼내 방문하지 않은 인접 노드 4, 5를 큐에 삽입하고 방문 처리

5. 더이상 큐에 남아있는 노드가 없을 때까지 반복

JS로 BFS 구현

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "G", "H", "I"],
  D: ["B", "E", "F"],
  E: ["D"],
  F: ["D"],
  G: ["C"],
  H: ["C"],
  I: ["C", "J"],
  J: ["I"]
};

const bfs = (graph, startNode) => {
  let visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야할 노드들

  needVisit.push(startNode); // 노드 탐색 시작

  while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
    const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
    if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
      visited.push(node); 
      needVisit = [...needVisit, ...graph[node]];
    }
  }
  return visited;
};

console.log(bfs(graph, "A"));
// ["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]

참조)
https://ryusm.tistory.com/48
https://www.youtube.com/watch?v=CJiF-muKz30&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=19