[Algorithm] BFS 알고리즘

DFS와 BFS

• 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 대표적인 그래프 탐색 알고리즘으로 DFS와 BFS가 있다.

JS Queue 구현하기 (FIFO)

class Queue {
 constructor() {
   this.items = {};
   this.headIndex = 0;
   this.tailIndex = 0;
  }
  // 큐에 원소 삽입
  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }
  // 맨 처음 원소 추출
  dequeue(){
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }
  // 다음으로 꺼내고자 하는 원소가 무엇인지 알려줌 
  peek() {
  	return this.items[this.headIndex];
  }
  // 큐의 길이 구하기 
  getLength(){
  	return this.tailIndex -this.headIndex;
  }
}

// 구현된 큐 사용
queue = new Queue();

queue.enqueue(5);
queue.dequeue();

그래프의 표현

• 2차원 배열(리스트)로 그래프를 표현한다.

1 ---- 2
| \    |
|  \   |
|   \  |
3 ---- 5
|    /
|   /
|  /
4 

• 인접 리스트

Node	Connected Nodes
1	2, 3
2	1, 5
3	1, 4, 5
4	3, 5
5	2, 3, 4

너비 우선 탐색(BFS)이란?

• 그래프 혹은 트리에서 모든 노드를 한번씩 탐색하기 위한 기본적인 방법
• 완전탐색을 수행하기 위해 사용할 수 있는 방법 중 하나
• (모든 간선의 길이가 동일할 때) 최단 거리를 탐색하기 위한 목적으로 사용할 수 있다.
• 큐 자료구조를 사용한다.
  - DFS는 스택, BFS는 큐를 사용한다.
  

너비 우선 탐색(BFS) 동작 방식

1. 시작 노드에 큐를 넣고 방문 처리한다
2. 큐에서 원소를 꺼내어 방문하지 않은 인접 노드가 있는지 확읺한다.
   ㄴ 있다면 방문하지 않은 인접노드를 큐에 삽입하고 방문 처리 한다
3. 2번 과정을 더 이상 반복할 수 없을 때까지 반복한다.

너비 우선 탐색(BFS) 사용 예시

1. 간선의 비용이 동일한 상황에서 최단 거리 문제를 해결하는 경우
2. 완전 탐색을 위해 사용한 DFS 솔루션이 메모리/시간 초과를 받아 BFS로 재시도 하는 경우

• DFS로는 일반적인 최단 거리 문제를 해결할 수 없다.
  되도록이면 BFS 사용

너비 우선 탐색(BFS)과 최단 경로

• BFS는 다익스트라 최단 경로 알고리즘과 유사한 특징이 있다.
  -> 다익스트라는 간선의 비용이 서로 다를 수 있을 때 사용 가능하다.

1) 다익스트라 알고리즘은 일반 큐 대신에 우선순위 큐를 사용한다.
2) 다익스트라는 특정 노드에 대하여 최단 거리 값이 갱신될 수 있다. (더 짧은 경로를 찾는 경우)

너비 우선 탐색(BFS) 소스 코드 예시

function bfs(graph, start, visited) {
  queue = new Queue();
  queue.enqueue(start);
  // 현재 노드 방문 처리 
  visited[start] = true;
  // 큐가 빌 때까지 반복
  while (queue.getLength() != 0) {
    // 큐에서 하나의 원소를 뽑아 출력하기 
    q = queue.dequeue();
    // 아직 방문하지 않은 인접한 원소들을 큐에 삽입
    for (i of graph[q]) {
      if (!visited[i]) {
        queue.enqueue(i);
        visited[i] = true;
      }
    }
  }
}