알고리즘, Tree, BFS

 

 

너비 우선 탐색(Breadth-First Search, BFS)은 그래프 또는 트리의 노드를 탐색하는 방법 중 하나입니다. BFS는 시작 노드에서 출발하여 인접한 노드를 먼저 탐색하고, 그 다음 인접한 노드들의 인접 노드를 탐색하는 방식으로 진행됩니다. 이는 주로 큐(queue) 자료 구조를 사용하여 구현됩니다.

BFS의 특징

1. 레벨별 탐색: BFS는 트리 또는 그래프의 레벨을 기준으로 노드를 탐색합니다. 즉, 첫 번째 레벨(루트 노드)에서 시작하여 다음 레벨로 진행합니다.
2. 최단 경로 탐색: 무방향 그래프에서 BFS는 시작 노드에서 다른 노드로 가는 최단 경로를 찾을 수 있습니다.
3. 큐 사용: BFS는 FIFO(First In, First Out) 특성을 가진 큐를 사용하여 다음에 탐색할 노드를 관리합니다.

BFS의 구현 (자바스크립트 예제)

트리와 그래프를 위한 BFS의 구현 예제를 살펴보겠습니다.

트리에서의 BFS 구현

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    let newNode = new Node(value);

    if (!this.root) {
      this.root = newNode;
      return this;
    }

    let current = this.root;

    while (true) {
      if (value === current.value) return undefined;

      if (value < current.value) {
        if (current.left === null) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } else if (value > current.value) {
        if (current.right === null) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
  }

  find(value) {
    if (!this.root) return false;

    let current = this.root;
    let found = false;

    while (current && !found) {
      if (value < current.value) {
        current = current.left;
      } else if (value > current.value) {
        current = current.right;
      } else {
        return true;
      }
    }

    return false;
  }

  BFS() {
    // Create a queue (this can be an array) and a variable to store the values of nodes visited
    // Place the root node in the queue
    // Loop as long as there is anything in the queue
    // Dequeue a node from the queue and push the value of the node into the variable that stroes the nodes
    // If there is a left property on the node dequeud - add it to the queue
    // If there is a right property on the node dequeued - add it to the queue
    // Return the variable that stores the values

    let visited = [];
    let queue = [];
    let currentNode = this.root;

    queue.push(currentNode);

    while (queue.length) {
      currentNode = queue.shift();
      visited.push(currentNode.value);

      if (currentNode.left) queue.push(currentNode.left);
      if (currentNode.right) queue.push(currentNode.right);
    }
    return visited;
  }
}

let tree = new BinarySearchTree();

console.log('tree is:', tree);
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(17);
tree.insert(7);
tree.insert(3);
tree.insert(13);
console.log('tree is:', tree);

console.log(tree.find(13));
console.log(tree.find(19));

console.log('BFS:', tree.BFS());

BFS의 동작 원리

1. 큐 초기화: 시작 노드를 큐에 추가합니다.
2. 큐가 빌 때까지 반복:
   • 큐에서 첫 번째 노드를 꺼내 현재 노드로 설정합니다.
   • 현재 노드를 방문 처리하고 결과 목록에 추가합니다.
   • 현재 노드의 모든 인접 노드를 큐에 추가합니다(이미 방문한 노드는 제외).
3. 반복 종료: 큐가 비면 탐색이 완료되고, 결과 목록을 반환합니다.

BFS의 시간 복잡도

BFS의 시간 복잡도는 그래프의 노드 수(V)와 엣지 수(E)에 따라 O(V + E)입니다. 이는 모든 노드와 엣지를 한 번씩 방문하기 때문입니다. 트리의 경우 노드 수가 n일 때, 시간 복잡도는 O(n)입니다.

BFS는 너비 우선으로 탐색하여 최단 경로를 찾는 문제에 적합하며, 모든 경로를 완전히 탐색해야 할 때 유용하게 사용됩니다.