DFSとBFS

DFS、BFSとは?

DFSとBFSはグラフィックをブラウズする方法です.
言葉だけで説明するのは難しい概念なので、絵を見て何がいいのかを見つけるのがいいです.
画像ソースリンク

DFS-深度優先ナビゲーション

迷宮では、死の道が現れるまで片側の壁に沿って深くナビゲートします.
死胡に遭遇すると同時に、最寄りの分かれ道に戻り、別の方向に沿って袋小路までまっすぐ行く方法.

DFSは、すべてのノードに適用されます.

BFS-幅優先ナビゲーション

まず迷宮の起点に近い点をナビゲートする方法.

の2つのパスの間の最短パスです.任意のパスを検索する場合は、このオプションを選択します.

DFS、BFS応用

バックアップ・ページのDFSとBFSに問題があります.
DFSとBFS
JSを使ってこの問題を解決しましょう.
無限ループを防止するには、DFSとBFSがノードにアクセスしているかどうかを確認する必要があります.

あらかじめ準備する

ソリューション関数には、頂点(ノード)の数、幹線の数、開始する頂点(ノードの番号)、および幹線の2つの頂点(ノード)の番号が含まれます.

function solution(N, M, V, MArray) {
  let answer = [];
  return answer;
}
const N = 4; //정점의 개수
const M = 5; //간선의 개수
const V = 1; //시작할 정점의 번호
const MArray = [
  [1, 2],
  [1, 3],
  [1, 4],
  [2, 4],
  [3, 4],
]; //간선이 연결하는 두 정점의 번호

console.log(solution(N, M, V, MArray));

このように見ると難しいと思います図に示すように、このような構造の図形です.

アクセスチェックの配列

を作成する

  let isVisit = new Array(N + 1).fill(false); //[ false, false, false, false, false ]

配列の個数をN+1とするのは,ノードが1から,配列のインデックスが0から始まるためである.この違いによる混乱を避けるために,アレイの大きさを1増やした.したがって、isVisit[0]は使用されない.

ex)1番ノードのアクセス権はisVisit[1]です.

falseで埋め込まれた配列が作成されました.ノードにアクセスすると、そのノードの配列がtrueになります.

ex)2ノードアクセス=>isVisit[2] = true

の幹線接続の2つの頂点の番号(配列)を隣接リスト

とする.
隣接リストの説明は、下のリンクで詳しく説明されています.を参照してください.
隣接リストリファレンス

function adjacency(N, MArray) {
  let arr = Array.from(new Array(N + 1), () => []); //[[],[],[],[],[]]
  for (let item of MArray) {
    arr[item[0]].push(item[1]);
    arr[item[1]].push(item[0]);
  }
  return arr;
}

function solution(N, M, V, MArray) {
 ......
  //인접리스트
  const adjacencyList = adjacency(N, MArray); //[ [], [ 2, 3, 4 ], [ 1, 4 ], [ 1, 4 ], [ 1, 2, 3 ] ]

隣接するリストを作成する関数は、個別に作成されます.
ノード数+1より大きい配列を作成し、空の配列で配列を埋めます.+1の理由は、アクセスチェックの理由と同じです.

現状:[[],[],[],[],[]]

問題が双方向パターンであり、a−>bまでの幹線が1本ある場合、b−>aまでの幹線も1本ある.
したがって、アレイ内の要素を1つずつ取り出す場合は、双方向のグラフィックであることを考慮します.

ex)[1,2]がポップアップされました.1−>2の幹線、2−>1の幹線が存在する.したがって、arr[1]の空の配列に2を追加し、arr[2]の空の配列に1を追加する.
=> [[],[2],[1],[],[]]

このようにしてすべてのMarrayを取り出すと、[ [], [ 2, 3, 4 ], [ 1, 4 ], [ 1, 4 ], [ 1, 2, 3 ] ]のような隣接リストが完了する.

ex)[ 2, 3, 4 ]は、ノード1(index 1)が2、3、および4番ノードに接続されていることを示す.

DFS-深度優先ナビゲーション

DFSは再帰関数を用いて問題を解決する.

	const startNode = V;
    const DFS = (curNode) => {
      isVisit[curNode] = true;
      answer.push(curNode);
      for (let subNode of adjacencyList[curNode]) {
        if (isVisit[subNode]) continue;
        DFS(subNode);
      }
    };
    DFS(startNode);

ゆっくり解きほぐそう

1.最初のDFSはstartNode人1を含む.
2.1番ノードにアクセスしているかどうかを確認します.isVisit[1] = trueisVisit === [ false, true, false, false, false ]3.どのような手順でナビゲーションを行うかを知るために、answer.push(1)を実行します.
answer === [1]4.隣接リストのインデックス1に対応する配列([2,3,4])から要素(サブノード)を1つずつ取り出す.
5.ノードが取り出されたかどうかを確認します(現在は2).if (isVisit[2]) continueノードが

にアクセスしている場合は、continueがノードをスキップし、次のノードを確認します.

ノードが

にアクセスしていない場合、DFSは2に入り、DFS関数を再実行します.

再帰関数も難点であるため,DFS(2)について議論する.
1.2番目のノードにアクセスしたかどうかを確認します.isVisit[2] = trueisVisit === [ false, true, true, false, false ]2.どのような手順でナビゲーションを行うかを知るために、answer.push(2)を実行します.
answer === [1,2]4.隣接リストのインデックス2に対応する配列([1,4])から要素(サブノード)を1つずつ取り出す.
5.取り出したノード(現在は1)がアクセスしたノードであるかどうかを確認します.if (isVisit[1]) continue6.1はアクセスしたノードです.したがって、次のノードを確認します.if (isVisit[4]) continue7.7は未アクセスのノードなので、4をDFSに入れてDFS関数を再実行します.

これにより、すべてのノードがアクセス登録を完了すると、最終的な答えは[1,2,4,3]を含む.

BFS-幅優先ナビゲーション

BFSはキューを使用して問題を解決する.

キューは、まずアレイに入る要素を含むデータ構造です.

	const startNode = V;
    const BFS = (curNode) => {
    isVisit[curNode] = true;
    answer.push(curNode);
    let queue = [curNode];
    while (queue.length > 0) {
      for (let subNode of adjacencyList[queue.shift()]) {
        if (isVisit[subNode]) continue;
        queue.push(subNode);
        isVisit[subNode] = true;
        answer.push(subNode);
      }
    }
  };
  BFS(startNode);
}

ゆっくり解きほぐそう

1.最初のDFSはstartNode人1を含む.
2.1番ノードにアクセスしているかどうかを確認します.isVisit[1] = trueisVisit === [ false, true, false, false, false ]3.どのような手順で探索したかを知るために回答してください.push(1)を行います.
answer === [1]4.queueという配列を作成し、1を挿入します.let queue = [1]5.キューに要素がないまでwhile文を作成します.while (queue.length > 0)ここから繰り返します.
5-1. adjacencyList[빼낸 요소 1]の配列([2,3,4])から1つの要素がキューの最初の要素として1つずつ取り出される.
queueの最初の要素1が削除されたため、現在のqueueは空です.
5-2. ノード(現在2)がアクセスされているかどうかを確認します.if (isVisit[2]) continueアクセスしたノードの場合は、次の要素を確認します.
アクセスしていないノードの場合
5-3. ノードをqueueに追加します.止まらないようにqueue.push(2)queue === [2]5-4. 2ノードにアクセスしているかどうかを確認します.isVisit[2] = trueisVisit === [ false, true, true, false, false ]5-5. どのような手順でナビゲーションを行うかを知るために、answer.push(2)を行います.
answer === [1,2]これにより、すべてのノードがアクセス登録を完了すると、最終的な答えは[1,2,3,4]を含む.
現在の問題では、1番ノードが2、3、4に接続されているため、queueは正しく使用されていません.
例えば、このような構造であれば

1->2->3の順序でナビゲートすると、for文は終了し、キューには[2,3]が含まれます.
queueに要素があるため、while文は再び要素を繰り返します.for (let subNode of adjacencyList[queue.shift()])は、2をキューに入れ、2のサブノード4を発見する.このようにして問題を解決する.