[Algorithm] BFS(Tree, Gragh)

広さ優先探索は幅優先探索のアルゴリズムである.
再帰的なDepth-First Search(深さ優先検索)を利用するのとは異なり、異なるアルゴリズムでアクセスする必要があり、このマシンルートでToy(午前1時間アルゴリズムで解く)に遭遇した場合、1時間以内には解けないため、ブログに記録して再学習します.
TreeのBFSとGraghのBFSを知る.

Tree BFS

TreeのBFSは深さを1つの層と見なし,層ごとにブラウズする.
(ナビゲーション順序:A>B>C>D>E>F>G>H>I>J>K)
First in First out構造を持つデータ構造キューを使用して実現されます.
最上位ノードを挿入した後、サブノードがある場合は後方に追加し続け、ナビゲートしたノードは削除する論理を使用します.サブノードは順番に後ろに積み上げられているので,層ごとに探索する.キュー内のすべてのノードが削除されると、論理は終了します.

function treeBFS(node) { // 최상단 노드를 인자로 받음
  let queue = [node]; // queue 생성
  const values = []; // 검색 값을 저장하는 배열
  while (queue에 노드가 담겨 있을 때까지) {
    // 1. queue의 첫 노드의 값을 values에 저장
    // 2. 첫 노드의 자식(children : 배열로 존재)을 순회하며 queue에 순차적으로 저장
    // 3. 첫 노드 삭제
  }
  return values;
}

Gragh BFS

GraghのBFSも同じキューを使用しているが、レイヤの概念は存在しないため、レイヤの概念に加えて、開始ノードの隣接(接続)ノードに基づいてキューに格納されてナビゲーションされる.
(ナビゲーション順序:A>B(A隣接)>D(A隣接)>C(D隣接)>E(D隣接)
キューに一度に入ったノードがキューに入るべきではないことに注意してください.木と違って、親子の区別がはっきりしていないからだ.

// 그래프는 각 노드의 인접정보가 나타나있는 2차원 배열의 인접리스트로 나타나져 있고, 각 노드의 값은 숫자로 가정

function graghBFS(gragh, start, visited) { // 그래프, 시작노드의 값, 현재 그래프의 노드개수 길이의 방문기록(false)을 담은 visitied 배열을 인자로 받음
  let queue = [start];
  visited[start] = true; // 시작노드는 true로 방문 처리
  const values = [];
  while (queue에 노드가 담겨있을 때까지) {
    // 1. start를 values에 저장 후 큐에서 삭제
    // 2. 그래프 start노드의 인접정보 중 visited에서 방문기록이 false인 값을 순서대로 큐에 삽입
    // 3. 큐에 삽입된 인접 노드들은 visited에서 true 처리
  }
  return values;
}