BFS 알고리즘은 DFS 알고리즘과는 다르게 넓이를 우선적으로 탐색한다.

모든 간선의 길이(비용)이 동일할때, 최단 거리를 탐색하기 위한 목적으로 사용할수 있다.

기본적으로 queue 자료구조 (선입 선출)를 사용한다.

- 구현 순서

1. 시작 노드를 큐에 넣고 방문처리 한다.

2. 큐에서 원소를 꺼내어서 방문하지 않은 원소가 있는지 확인한다.

• 있다면, 방문하지 않은 원소를 큐에 넣고 방문처리 한다.

3. 2번 과정이 반복 될수 없을때까지 반복한다.

기본적으로 BFS 알고리즘은 최단거리 문제를 해결할때 사용할수 있다.

DFS와 BFS 알고리즘 모두 그래프 탐색 목적으로 사용할수는 있으나, 보통 DFS에서 시간초과가 나는 경우에 BFS 알고리즘으로 해결할 수있다.

DFS 알고리즘으로는 보통 최단거리 문제를 해결할 수 없다.

(DFS 알고리즘으로 해결할수 있는 문제는 BFS 알고리즘으로도 해결할수 있기에, BFS 알고리즘을 최대한 연습해서 구현 능력을 향상 시켜 놓는 것이 낫다.)

위 같은 그래프 노드가 있다고 가정해본다면

1. A가 queue 에 들어간다.

2. queue 에서 A를 꺼내어서, 인접한 노드 중에서 방문하지 않은 노드인 B, C, D를 방문한다.

3. [B, C, D] 순서대로 들어갔으므로, queue에서 B를 꺼내서 B와 인접한 노드중에서 방문하지 않은 노드를 탐색한다.

4. 없다면 C를 꺼내서, C와 인접한 노드중에서 방문하지 않은 노드인 E, F 를 방문한다. (queue에 넣어준다.)

5. 그 후에 D를 꺼내어서, D와 인접한 노드중에서 방문하지 않은 노드인 G를 방문한다.

6. 그 후 E와 인접한 노드중에서 방문하지 않은 노드인 H를 방문한다.

총 방문 순서는 A => B => C => D => E => F => G => H 가 된다.

---

BFS는 간선의 비용이 동일할때, 최단 거리 문제를 해결하기 위해서 사용이 가능하다.

다익스트라 알고리즘과 유사한데, 다익스트라 알고리즘은 각 간선의 비용이 다를때 사용이 가능하고 큐가 아닌 우선 순위 큐를 사용한다.

또한 특정 노드에 대해서 더 짧은 경로를 찾았을때, 최단거리 값이 갱신이 될수 있다.

결국 이 다익스트라 알고리즘도 BFS를 기반으로 구현하기 때문에 알아두어야한다.

function bfs(graph, start, visited) {
  queue = new Queue();

  queue.enqueue(start); // 큐에 삽입

  visited[start] = true; // 방문처리

  while (queue.length) {
    vertex = queue.dequeue(); // 큐에서 해당 노드 꺼내오기

    console.log(vertex);

    // 해당 노드와 인접한 노드중에서 방문하지 않은 노드가 있다면
    for (let i of graph[vertex]) {
      if (!visited[i]) {
        // 큐에 넣어주기
        queue.enqueue(i);

        // 방문하지 않은 노드 방문 처리
        visited[i] = true;
      }
    }
  }
}

여기선 queue 를 직접 구현했다고 가정했지만, 실제 문제에서는 배열이어도 상관 없다.