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

yezo cha·2021년 8월 26일

BFS TIL 자료구조

Data Structure & Algorithm

목록 보기

8/15

그래프 탐색이란?
하나의 정점에서 시작해서 그래프의 모든 정점들을 한번씩 탐색하는 것을 말한다.

BFS

그래프 전체를 탐색하는 방법 중 하나.
루트 노드 (혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법.
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회방법.
종이에 먹물이 퍼지는 것과 같음.
즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색한다 !
BFS가 진행될수록 탐색 범위는 출발점에서 멀어진다.

주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용하는 방법이다.
(최단 경로, 길찾기)
방문한 노드들을 차례대로 저장한 후 꺼낼 수 있는 자료구조인 Queue를 사용한다.

queue

Queue는 선입선출(FIFO, Fisrt In First Out) 자료구조.
먼저 들어온 것이 먼저 나간다.
고속도로 톨게이트를 생각하자.

특징
- 재귀적으로 동작하지 않는다.
- 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.
  - 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
장점
- 로직이 단순하다.
- 최초 발견 루트를 최단 경로라고 보장할 수 있다.
- 노드의 숫자가 적고, 깊이가 얕은 경우 -> 단순검색속도가 DFS보다 빠르다.
단점
- 비교적 많은 저장 공간이 필요하다.

BFS 알고리즘 구현방식

큐를 활용해서 구현.

a 노드(시작 노드)를 방문. (방문한 노드 체크)
- 큐에 방문한 노드를 삽입. enqueue
- 초기 상태의 큐에는 시작 노드만 저장되어 있다.
  - 즉, a노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다 !
큐에서 꺼낸 노드와 인접한 노드들을 모두 차례대로 방문.
- 큐에서 꺼낸 노드를 방문
- 큐에서 꺼낸 노드와 인접한 노드들을 방문
  - 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다. dequeue
- 큐에 방문된 노드를 삽입. enqueue
큐가 다 소진될 때까지 계속 반복.

void search(Node root) {
  Queue queue = new Queue();
  root.marked = true; // (방문한 노드 체크)
  queue.enqueue(root); // 1-1. 큐의 끝에 추가

  // 3. 큐가 소진될 때까지 계속한다.
  while (!queue.isEmpty()) {
    Node r = queue.dequeue(); // 큐의 앞에서 노드 추출
    visit(r); // 2-1. 큐에서 추출한 노드 방문
    // 2-2. 큐에서 꺼낸 노드와 인접한 노드들을 모두 차례로 방문한다.
    foreach (Node n in r.adjacent) {
      if (n.marked == false) {
        n.marked = true; // (방문한 노드 체크)
        queue.enqueue(n); // 2-3. 큐의 끝에 추가
      }
    }
  }
}

let bfs = function (node) {
    // TODO: 노드의 탐색을 treeBFS 탐색 순으로 배열에 담아내자
    let result = [];
    let queue = [node]; // 조회할 노드를 순차적으로 넣는다.

    // 조회할 노드가 없을때까지
    while (queue.length) {
        let target = queue.shift();
        result.push(target.value);
        // 자식 노드들을 순차적으로 queue에 쌓아준다.
        for (let node of root.children) {
            queue.push(node);
        }

    }
    return result;
};
let Node = function (value) {
    this.value = value;
    this.children = [];
};

// 위 Node 객체로 구성되는 트리는 매우 단순한 형태의 트리.
// membership check(중복 확인)를 따로 하지 않는다.
Node.prototype.addChild = function (child) {
    this.children.push(child);
    return child;
};