BFS

class Queue {
    constructor() {
      this.items = {};
      this.frontIndex = 0;
      this.backIndex = 0;
    }
  
    enqueue(item) {
      this.items[this.backIndex] = item;
      this.backIndex++;
    }
  
    dequeue() {
      if (this.isEmpty()) return undefined;
      
      const item = this.items[this.frontIndex];
      delete this.items[this.frontIndex];
      this.frontIndex++;
      return item;
    }
  
    isEmpty() {
      return this.frontIndex === this.backIndex;
    }
  
    size() {
      return this.backIndex - this.frontIndex;
    }
}

// 직접 구현한 Queue 클래스를 사용한 BFS
function bfs(g, s, visit) {
    const q = new Queue();
    q.enqueue(s);
    
    while (!q.isEmpty()) {
      const current = q.dequeue(); // O(1) 연산
      console.log(current);
      
      for (const n of graph[current]) {
        if (!visit[n]) {
            visit[n] = true;
            q.enqueue(n);
        }
      }
    }
    
    return visited.size; // 방문한 노드 수 반환
}

let graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7],
]
  
let visited = [...Array(9).fill(false)];
bfs(graph, 1, visited);

결과 : 123817456