너비우선탐색(BFS)

너비우선탐색(BFS)

그래프 탐색을 위한 알고리즘이다.

• 그래프 탐색 : 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 의미한다. (ex 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지)

너비 우선 탐색(Breadth First Search)

너비 우선 탐색(Breadth First Search): 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식

• 시작 정점에서 가까운 정점을 먼저 방문하고 멀리 떨어진 정점을 나중에 방문하는 방법이다.
• 두 장소의 최단거리, 혹은 친구추천을 위해 사용된다.
• 갔던 곳과 가지 않은 곳을 위해서 두 개의 큐(queue)가 필요하다. 이를 통해 무한루프를 방지한다.
• 큐를 이용하므로 선입선출의 원칙을 지킨다.
• 깊이 우선 탐색보다 조금 더 복잡하다.

너비 우선 탐색(Breadth First Search)과정

1. a 노드(시작 노드)를 방문한다. (방문한 노드 체크)
   • 큐에 방문된 노드를 삽입(enqueue. push)한다.
   • 초기 상태의 큐에는 시작 노드만이 저장된다.
     (즉, a 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃노드들을 방문한다.)
2. 큐1에서 꺼낸 노드과 인접한 노드들을 모두 차례로 방문한다.
   • 큐에서 꺼낸 노드를 방문한다.
   • 큐에서 커낸 노드과 인접한 노드들을 모두 방문한다.
     (인접한 노드가 없다면 큐1의 첫번째 요소 노드를 꺼낸다(dequeue).)
   • 큐에 방문된 노드를 삽입(enqueue)한다.
     큐가 빌 때까지 (queue.length = 0 이 될 때까지)

방문을 마친 노드들은 큐1에 , 방문을 해야하는 노드들은 큐2에 저장해둔다. 만약 방문해야하는 노드가 큐1에 이미 존재한다면 건너 뛰고 다음 노드로 넘어간다.

예시

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'G', 'H', 'I'],
  D: ['B', 'E', 'F'],
  E: ['D'],
  F: ['D'],
  G: ['C'],
  H: ['C'],
  I: ['C', 'J'],
  J: ['I']
};


const bfs = (graph, startNode) => {
  let visited = []; // 방문을 마친 노드들
  let needVisit = []; // 방문해야할 노드들

  needVisit.push(startNode); // 노드 탐색 시작

  while (needVisit.length !== 0) { // 방문해야할 노드가 남아있다면
    const node = needVisit.shift(); // queue이기 때문에 선입선출의 원칙을 지켜준다.
    if (!visited.includes(node)) { // 해당 노드가 방문된 적 없다면
      visited.push(node); //  큐에 삽입
      needVisit = [...needVisit, ...graph[node]];  새롭게 방문해야 할 노드를 큐에 삽입해준다.
    }
  }
  return visited;
};

console.log(bfs(graph, "A"));
["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]

느낀 점

코플릿에서 BFS문제가 있어서 BFS가 뭔지부터 시작해 공부했다...수박 겉핥기 식이긴 한데 공부했더니 풀리긴 했다. 근데 이제 소요시간을 2시간 40분정도 곁들인.
많이 어렵다. 많이 어려운만큼 많이 공부해야해.