BFS 너비 우선 탐색

그래프 탐색은 한 정점에서 차례대로 모든 정점을 방문하는 것

너비 우선 탐색(Breadth First Search)은 그래프 탐색방법 중 하나이다.

BFS의 구현은 큐를 사용하여 선입선출(FIFO)방식으로 구현하면 된다.
구현 알고리즘은 다음과 같다.
1. 시작 노드를 큐에 삽입(push)
2. 큐에서 노드를 하나 꺼낸다.(shift)
3. 방문처리(visitid) 후 인접노드를 큐에 삽입(push)
그 다음 2,3번을 반복하다가 모두 방문처리 되어 큐가 비면 탐색을 종료한다.

입출력 예

         A
      /     \
     B       C
    / \      /\
   D  E     F  G
  /\  /\   /\  /\
 H I J K  L M  N O

출력 순서

A - B - C - D - E - F - G - H - I - J - K - L - M - N - O

예시 코드

• 그래프 데이터

// ['노드', '연결된 노드']
const bfsArr = [
  ['B', 'ADE'],
  ['F', 'CLM'],
  ['A', 'BC'],
  ['L', 'F'],
  ['G', 'CNO'],
  ['C', 'AFG'],
  ['D', 'BHI'],
  ['I', 'D'],
  ['J', 'E'],
  ['K', 'E'],
  ['E', 'BJK'],
  ['N', 'G'],
  ['O', 'G'],
  ['M', 'F'],
  ['H', 'D'],
];

• BFS 구현

const solution = (arr) => {
  const answer = 'ABCDEFGHIJKLMNO';
  /** BFS: 너비 우선 탐색
   *           A
   *        /    \
   *      B       C
   *    /  \    /  \
   *   D   E   F   G
   *  /\  /\  /\  /\
   * H I J K L M N O
   * A-B-C-D-E-F-G-H-I-J-K-L-M-N-O
   */
  const obj = arr.reduce((acc, cur) => {
    acc[cur[0]] = cur[1];
    return { ...acc };
  }, {});
  // console.log(obj);
  // queue 를 이용해서 순서대로 출력
  const queue = [];
  const visited = [];
  queue.push(['A', obj['A']]); // start node is 'A'
  while (queue.length) {
    const [node, link] = queue.shift();
    if (!visited.includes(node)) visited.push(node);

    const linkedNodes = link.split('');
    for (let i = 0; i < linkedNodes.length; i++) {
      if (visited.filter((v) => v[0] === linkedNodes[i]).length > 0) continue;
      queue.push([linkedNodes[i], obj[linkedNodes[i]]]);
    }
  }
  console.log(visited);
  console.log(visited.join('') === answer);
};