• Breadth-First Search, Graph의 가까운 Node부터 탐색하는 방식
• Queue 기반으로 동작하며, Graph 레벨별로 탐색
• 가까운 노드부터 탐색하기 때문에 최단 경로를 보장
  • 단, 간선 가중치가 모두 같을 때(사실상 무가중치)만 성립하며, 가중치가 서로 다르면 다익스트라가 필요
• 사용처 : 최단 경로 탐색, 소셜 네트워크의 친구 추천(n촌 관계), 네트워크 브로드캐스트 등
• 시간 복잡도 : O(V + E), V는 노드 수, E는 간선 수
• 공간 복잡도 : O(V)
• 방문 표시는 Queue에 넣는 시점에 해야 함, 꺼낼 때 표시하면 같은 노드가 큐에 여러 번 쌓임
• 메모리는 가장 넓은 레벨의 노드 수에 비례하므로, 넓고 얕은 그래프에서는 DFS보다 메모리를 많이 씀
• JavaScript 배열의 shift()는 O(n)이라 노드가 많으면 병목이 됨, 실무에선 head 인덱스를 옮기거나 Deque를 씀

function bfs(graph, current, visited) {
	let queue = []
	queue.push(current)

	visited[current] = true
	while (queue.length) {
		const first = queue.shift()
		for (let i=0; i < graph[first].length; i++) {
			const value = graph[first][i]
			if (!visited[value]) {
				queue.push(value)
				visited[value] = true
			}
		}
	}
}

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

bfs(graph, 1, visited)