BFS/DFS


グラフィックを参照するには、BFSとDFSを使用します.
グラフとは?
  • 頂点(ノード)およびその頂点を接続する幹線(エッジ)からなる資料構造.
  • グラフィックナビゲーション>1つの頂点から順にすべての頂点
  • にアクセスします.

    幅優先ナビゲーション


    コンセプト


    まず、
  • 頂点と同じレベルにあるノードを参照します.
    (できるだけ広く移動し、移動を継続できない場合は下に移動)
  • 特長

  • の2つのキューを使用します.
  • 本に近いノードから探すため,最短距離の探索に有用である.
  • targetがルートに近いと予想される場合に使用します.
  • キュー実装
  • 使用例

  • 地図アプリケーションから特定の場所への最短距離ガイド
  • おすすめ友達
  • 検索範囲は大きくなく、検索起点から遠くない
  • const graph = {
      A: ["B", "C"],
      B: ["A", "D"],
      C: ["A", "G", "H", "I"],
      D: ["B", "E", "F"],
      E: ["D"],
      F: ["D"],
      G: ["C"],
      H: ["C"],
      I: ["C", "J"],
      J: ["I"]
    };
    
    const bfs = (graph, startNode) => {
      let visited = []; // 탐색을 마친 노드들
      let needVisit = []; // 탐색해야할 노드들
    
      needVisit.push(startNode); // 노드 탐색 시작
    
      while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
        const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
        if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
          visited.push(node); 
          needVisit = [...needVisit, ...graph[node]];
        }
      }
      return visited;
    };
    
    console.log(bfs(graph, "A"));
    // ["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]

    深度優先ナビゲーション


    コンセプト

  • 時の子供たちが先に探る方法
    (できるだけ深く、深く入るところがなければ横に移動)
  • 特長

  • は、1つのキューと1つのスタックを使用します.
  • ノード(または任意のノード)から開始し、次の四半期までに
  • ブランチを完全にナビゲートします.
  • BFSよりも簡単に実施できるが、探索速度はBFSよりも
  • 遅い.
  • は再帰的またはスタックによって
  • を実現する.

    使用例

  • すべてのノードにアクセスする場合は、
  • にアクセスします.
  • 迷宮ゲームで経路が存在するか否かを判別する際に非常に有用である
  • .
  • パスの特徴を格納する必要がある場合(aからbまでのパスを探し、パスに同じ数字がないなど)、
  • .
  • 検索するグラフィックが非常に大きい場合は、
  • を考慮してください.
    const graph = {
      A: ["B", "C"],
      B: ["A", "D"],
      C: ["A", "G", "H", "I"],
      D: ["B", "E", "F"],
      E: ["D"],
      F: ["D"],
      G: ["C"],
      H: ["C"],
      I: ["C", "J"],
      J: ["I"],
    };
    
    // (graph, 시작 정점)
    const dfs = (graph, startNode) => {
      let needVisitStack = []; // 탐색을 해야 할 노드들
      let visitedQueue = []; // 탐색을 마친 노드들
    
      needVisitStack.push(startNode);
    
      // 탐색을 해야 할 노드가 남아 있다면
      while (needVisitStack.length !== 0) {
        const node = needVisitStack.pop();
        if (!visitedQueue.includes(node)) {
          visitedQueue.push(node);
          needVisitStack = [...needVisitStack, ...graph[node]];
        }
      }
    
      return visitedQueue;
    };
    
    console.log(dfs(graph, "A"));
    
    // ["A", "C", "I", "J", "H", "G", "B", "D", "F", "E"]
    🔺BFSもDFSもノード数+幹線数の複雑さを持つ.
    コメントとソース1
    コメントとソース2
    コメントとソース3