[알고리즘] BFS

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

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법을 의미한다.

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.,
• 사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

DFS의 경우 BFS보다 좀 더 복잡하다.

BFS 방문하는 방법

BFS의 특징

• 시작 노드에서 시작해서 거리에 따라 단계별로 탐색하기 때문에 직관적이지 않은 면이 있다.
• 재귀적으로 동작하지 않는다.
• 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 그렇지 않으면 무한 루프에 빠질 위험이 있다.
• BFS는 방문한 노드를 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
  • 즉, 선입선출 원칙으로 탐색하며, 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.

BFS 구현 방법

1. 시작하고자 하는 노드를 Queue에 넣는다.
2. 현재 큐의 노드를 빼고, 방문한 기록을 남긴다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않는 노드를 큐에 추가한다.
4. 2-3을 반복한다.
5. Queue가 비면 탐색을 종료한다.

import { Queue } from "./queue";

function BFS(graph: number[][], start: number, visited: boolean[]) {
  const queue = new Queue();
  queue.enQueue(start);
  visited[start] = true;

  while (queue.size()) {
    const v = queue.deQueue();
    console.log(v);

    for (const node of graph[v]) {
      if (!visited[node]) {
        queue.enQueue(node);
        visited[node] = true;
      }
    }
  }
}
const graph = [[1, 2, 4], [0, 5], [0, 5], [4], [0, 3], [1, 2]];
const visited = Array(6).fill(false);
BFS(graph, 0, visited);

 

export class Queue {
  private store;
  private front: number;
  private rear: number;

  constructor() {
    this.store = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    if (this.store[this.rear] === undefined) {
      return null;
    } else {
      return this.rear - this.front + 1;
    }
  }
  enQueue(value) {
    if (this.size() === null) {
      this.store["0"] = value;
    } else {
      this.rear += 1;
      this.store[this.rear] = value;
    }
  }

  deQueue() {
    let temp;
    if (this.front === this.rear) {
      temp = this.store[this.front];
      delete this.store[this.front];
      this.front = 0;
      this.rear = 0;
      return temp;
    } else {
      temp = this.store[this.front];
      delete this.store[this.front];
      this.front++;
      return temp;
    }
  }
}

 

BFS의 시간 복잡도

• 인접 리스트로 표현된 그래프: O(N+E)
• 인접 행렬로 표현된 그래프: O(N^2)

참조

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

https://chamdom.blog/bfs-using-js/