Tree BFselect(너비 우선 탐색)

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

Tree {
  value: 0,
  children: [
    Tree { value: 1, children: [Array] },
    Tree { value: 2, children: [Array] }
  ]
} // 들어오는 형태

1.  시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

2. 즉, 깊게 탐색하기 전에 넓게 탐색하는 것

3. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을때 이 방법을 선택함

Tree.prototype.BFSelect = function(filter) {
  let result = [];
  let queue = [];
  let nextNode;

  queue.push({
    depth: 0,
    node: this
  });

  while (queue.length > 0) {
    nextNode = queue.shift();

    if (nextNode.node.children.length > 0) {
      for (let i = 0; i < nextNode.node.children.length; i++) {
        queue.push({
          depth: nextNode.depth + 1,
          node: nextNode.node.children[i]
        });
      }
    }

    if (filter(nextNode.node.value, nextNode.depth)) {
      result.push(nextNode.node.value);
    }
  }

  return result;
};

너비 우선 탐색의 특징

• BFS는 재귀적으로 동작하지 않는다
• 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다
  이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다
• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐를 사용한다
  즉, 선입선출(FIFO) 원칙으로 탐색한다

너비 우선 탐색 과정

• 깊이가 1인 모든 노드를 방문하고 나서 그 다음에는 깊이가 2인 모든 노드를,
  그 다음에는 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마친다