[그래프 탐색] BFS

BFS(Breadth-First Search)  - 너비 우선 탐색

 

queue - 선입 선출 (FIFO - First In First Out) 

 

작동 방식

1. 시작 노드를 큐에 넣는다. 
2. 큐가 빌 때까지 아래과정을 반복한다.
   1. 큐 맨 위 노드를 꺼낸다.
   2. 해당 노드 방문 여부 체크 => 했다면 패스
   3. 방문 안했다면, 이를 방문 처리 후 해당 정점과 이어진 정점들을 큐에 넣는다.

예시 1 

 

경로

경로 - 위: dfs / 아래: bfs

스택 / 큐

dfs / bfs

예시 2 

 

경로

위: dfs / 아래: bfs

스택 / 큐

dfs / bfs

 

 

코드

const bfs = (startNode) => {
  let visited = new Set();
  let needVisit = [startNode]; //큐역할
  let results = [];
  while (needVisit.length) {
    let node = needVisit.shift(); //맨 앞에서 빼기
    if (!visited.has(node)) {
      // 해당 노드 방문이 처음이라면
      results.push(node);
      visited.add(node);
      if (graph[node]) needVisit = [...needVisit, ...graph[node]]; //맨 뒤에 넣기
    }
  }
  console.log(results.join(" "));
};

 

참고 문제

 

https://www.acmicpc.net/problem/1260