[알고리즘] BFS 구현 - javascript

✅ BFS : 너비우선탐색

• 시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어져있는 노드를 나중에 방문하는 탐색 방법
• 큐 자료구조를 이용
• 자바스크립트의 경우 내장 라이브러리에 큐가 없기 때문에 직접 구현해야함

✔️ 큐 (shift 이용)

• queue를 배열에 담아서 shift메서드를 활용하여 구현한 코드

function bfs(graph, start, visited) {
  const queue = [];
  queue.push(start);
  visited[start] = 1;

  while (queue.length > 0) {
    let v = queue.shift();
    console.log(v);

    for (let node of graph[v]) {
      if (!visited[node]) {
        queue.push(node);
        visited[node] = 1;
      }
    }
  }
}

const graph = [[1, 2, 3], [0, 6], [0], [0, 4, 5], [3], [3], [1]]; // 인접 리스트
const visited = Array(graph.length).fill(0); // 방문 여부 확인 리스트

bfs(graph, 0, visited);

✔️ 큐 (class Queue 이용)

// class Queue
class Queue {
  constructor() {
    this.store = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    if (this.store[this.rear] === undefined) {
      return 0;
    } else {
      return this.rear - this.rear + 1;
    }
  }

  push(value) {
    if (this.size() === 0) {
      this.store['0'] = value;
    } else {
      this.rear += 1;
      this.store[this.rear] = value;
    }
  }

  popleft() {
    let temp;
    if (this.front === this.rear) {
      temp = this.store[this.front];
      delete this.store[this.front];
      this.front = 0;
      this.rear = 0;
      return temp;
    } else {
      temp = this.store[this.front];
      delete this.store[this.front];
      this.front += 1;
      return temp;
    }
  }
}

function bfs(graph, start, visited) {
  const queue = new Queue();
  queue.push(start);
  visited[start] = 1;

  while (queue.size()) {
    const v = queue.popleft();
    console.log(v);

    for (const node of graph[v]) {
      if (!visited[node]) {
        queue.push(node);
        visited[node] = 1;
      }
    }
  }
}

const graph = [[1, 2, 3], [0, 6], [0], [0, 4, 5], [3], [3], [1]]; // 인접 리스트
const visited = Array(graph.length).fill(0); // 방문 여부 확인 리스트

bfs(graph, 0, visited);

✔️ 기타

• 처음에 while(queue)로 해서 풀었더니 graph[v]가 iterable하지 않다는 에러가 계속 떴다.
• while(queue)는 queue의 존재여부에 따라 true를 반환하기 때문에 queue가 빈 배열이 되었는데도 계속 while문을 돌아서 생겼던 문제였다.
• while(queue.length > 0)으로 바꿔주니 오류가 해결되었다.
• 조금 더 많이 생각하자!!

참고 블로그

[알고리즘] JavaScript로 구현하는 BFS