[JavaScript] BFS

BFS

BFS는 Queue 자료구조를 이용하여 다음과 같이 구현할 수 있다.

const bfs = (here) => {
  const q = new Queue()
  q.push(here)
  visited[here] = true
  
  if (!q.isEmpty()) {
    const p = q.pop()
   	graph[p].forEach(there => {
      if (!visited[there]) {
       	q.push(there)
        // 혹은 visited[there] = true
        visited[there] = visited[here] + 1
      }
    })
  }
}

Queue에 대해 간단하게 구현해보자

자바스크립트 배열 + shift + push를 쓰지 않는 이유

shift 연산은 O(N)의 시간 복잡도를 가지기 때문이다.

Queue

class Queue {
  constructor() {
    this.arr = []
    this.rear = 0
    this.front = 0
  }
  
  push(item) {
	this.arr[rear++] = item
  }
  
  pop() {
   	return this.isEmpty() ? undefined : this.arr[front++] 
  }
  
  isEmpty() {
   	return this.front === this.rear 
  }
}