[アルゴリズム]DFS/BFS


検索(Search)とは、大量のデータから所望のデータを探すプロセスである.
典型的なグラフィックブラウズアルゴリズムにはDFS/BFSがある.
歌壇によく登場する.
事前に知っておく必要があるデータ型

データ構造


データ構造でーたこうぞう:スタックスタックスタック
  • データを先に入力して出力するデータ構造.
  • 入口および出口は、同じ形でスタックを可視化することができる.
  • (主に箱を積み上げる例ですが、上から出さないと真ん中や下から出しにくいです)
    スタック動作の例
    挿入
  • (5)-挿入(2)-挿入(3)-挿入(7)-削除(1)-挿入(4)-削除(
  • )
    5 2 3 7まで削除7へ
    5 2 3から1、4を再挿入
    5 2 3 1 4で最後の4を削除します.
    5 2 3 1になります
    私は主にJSを使用していますが、Pythonでは、List資料型自体がスタック資料構造を使用するのに適しています.(追加のライブラリは不要)
    データ構造でーたこうぞう:キューキューキューキューキューキューキューキューキューキューキューキュー
    先進的なデータ先行の資料構造.
    QUEは入口も出口も穴のあるトンネルのように可視化できる.
    一般的に銀行窓口などにたとえることができ、行列などを考えると分かりやすい.
    キューの動作例
    挿入
  • (5)-挿入(2)-挿入(3)-挿入(7)-削除(1)-挿入(4)-削除(
  • )
    パイプラインのように考えるともっと気持ちがいいです.
    5入ってきました.
    5分の2の人が入ってきた
    3/2/5このように左から入る(実は方向は本人の理解にかかっている)
    7/3/2/5がこのようにパイプラインに入ると、方向は左側になります.
    Q資料構造の特性を満たすには,まず入った5は先に退出しなければならない.
    だから削除コマンドを実行すると
    5出かけました.
    7 3 2残りは、その後挿入し、左側(つまり入る入り口)に追加します.
    1 7 3 2
    4 1 7 3 2
    再削除コマンドの使用
    2落ちた
    4 1 7 3は最後のパイプラインに残ります.(実際には、主にキューのように動作するため、ほとんど同じ意味で「パイプライン」という言葉を使用するサービスを見ることができます.)
    またPythonについてのヒントがあれば
    from collections import deque 
    dequeライブラリを使用しましょう.
    このツールは、Listデータ型を用いて実現することができるが、時間的複雑度が高く、効率が低い.
    だからデッキ?ライブラリを書くことをお勧めします.
    「厳密には、インデックス・ライブラリはスタックとキューのデータ構造の利点を統合したデータ構造です.」
    時間の複雑さじかんのふくざつさ:一定時間ていじょうじかん
    append、popleftの使用はPythonユーザー間の慣例のように通用します.

    さいきかんすう

  • 再帰関数とは、自分の関数を再呼び出しすることです.
  • 単純形状の再測定関数の例
  • 「再帰関数を呼び出します.」無限出力文字列なし.
  • がある程度出力されると、最大再帰深さが超えたメッセージが出力される.
  • ある程度符号化すると、
    アクセントたくさんの話が聞こえます
    私個人にとって、いくつかの実現では、私は再帰的に実現していません.
    しかし、Web開発では、パフォーマンスの最適化がますます重要になり、新しい開発者にとって相対的に少ないスキル要件になる可能性があります.
    最終的にどれだけ見ることができますか.
    再帰関数の終了条件
    問題解決で
  • 再帰関数を使用する場合は、再帰関数の終了条件を指定する必要があります.
  • 終了条件が正しく指定されていない場合は、関数が無限に呼び出される可能性があります.
    終了条件を含む再帰関数の例

  • 
    function recursive(i) {
      // 100번째 호출을 했을 때 종료되도록 종료 조건 명시
      if(i===100) {
        return; 
      }
      console.log(`${i}번째 재귀함수에서 ${i + 1}번째 재귀함수를 호출합니다.`);
      recursive(i + 1);
      console.log(`${i}번째 재귀함수를 종료합니다.`);
    }
    
    recursive(1)
    
    // 결과 예측
    // 1번째 재귀함수에서 2번째 재귀함수를 호출합니다.
    // 2번째 재귀함수에서 3번째 재귀함수를 호출합니다.
    // 3번째 재귀함수에서 4번째 재귀함수를 호출합니다.
    // .....(중략)
    // 99번째 재귀함수에서 100번째 재귀함수를 호출합니다.
    // -------이때가 종료조건 if를 충족하므로 return 되면서
    // 99번째 재귀함수를 종료합니다.
    // 98번째 재귀함수를 종료합니다.
    // 97번째 재귀함수를 종료합니다.
    // .....(중략)
    // 1번째 재귀함수를 종료합니다.
    
    プラント実装例
  • n! = 1x2x3x ... x (n-1) x n
  • 数学では0!第1課の双曲線コサインを返します.
  • function factorial_iterative(n) {
      let result = 1;
      // 1부터 n까지의 수 차례대로 곱하기
      for(let i=0; i<n+1; i++) {
        result *= i; // result = result * i ;
      }
      return result;
    }
    
    function factorial_recursive(n) {
      if(n<=1) { // n이 1이하인 경우 1을 반환
        return 1; 
      }
      // n! = n * (n-1)!를 그대로 코드로 작성하기
      return n * factorial_recursive(n - 1)
    }
    
    factorial_iterative(5) //120
    factorial_recursive(5) //120
    最大公約数計算例(ユークリッドアーク抽出法)

  • 2つの自然数の最大承諾数を求める典型的なアルゴリズムにはユークリッドアーク除去法がある.

  • ユークリッドアークほう
  • の2つの自然数A,Bについて、(A>B)AをBで割った残りの数をRと呼ぶ.
  • の場合、AとBの最大承諾数はBとRの最大承諾数に等しい.

  • ユークリッドアーク抽出法の考え方を直接再帰関数に書くことができる.
  • 例:GCD(192162)
  • ステージ
    A
    B
    1
    192
    162
    2
    162
    30
    3
    30
    12
    4
    12
    6
    
    function GCD(a, b) {
      if(a%b===0) {
        return b;
      }else{
        return GCD(b, a%b);
      }
    }
    
    console.log(GCD(192, 162)) // 6
    
    再帰関数の使用に関する注意事項
  • 再帰関数を用いて,複雑なアルゴリズムの記述を簡略化できる.
  • しかし、他の人には理解しにくいコードになる可能性があるので、慎重に使用する必要があります.
  • すべての再帰関数は、重複文を使用して同じ機能を実現することができる.
  • 再帰関数は、繰り返し文よりも有利であり、不利である可能性があります.
  • コンピュータが関数を連続的に呼び出すと、コンピュータメモリのスタックフレームが積み上げられます.
    したがって、
  • は、スタックを使用する必要がある場合、スタックライブラリを実装するのではなく、通常、再帰関数を使用する.
  • ビットの特性のため、代表的なのはDFSをより簡潔で短いコードに記述するためであり、通常は再帰関数のみを用いてDFSを実現する.
  • DFS


    DFS(Depth-First Search)
  • DFSは深さ優先ナビゲーションとも呼ばれ、グラフィックで深さを優先的に検索するアルゴリズムである.
  • DFSはスタック構造(または再帰関数)を使用し、具体的な操作手順は以下の通りである.
  • ナビゲーション開始ノードをスタックに挿入し、アクセス処理を行う.
  • スタック内の隣接ノードがアクセスしていない場合は、スタックに格納してアクセス処理を行います.アクセスされていない隣接ノードがない場合は、スタックから最上位ノードを取り出します.
  • ステップ
  • は、2番目の処理が実行されなくなるまで繰り返される.
  • アクションの例
  • [Step 0]グラフィックを準備します.(アクセス条件:番号の低い隣接ノードから)
  • 開始ノード:1

  • まず、幹線は無方向図です.
    どのノードからアクセスしますか?標準=質問の内容によって異なる場合があります.
    この例では、番号の低い隣接ノードから開始します(通常は共通の基準です).
    「1」を
  • [Step 1]開始ノードとしてスタックに挿入しアクセス処理を行う.
  • [Step 2]スタックの最上位ノード「1」には、アクセスされていない隣接ノード「2」、「3」および「8」がある.
  • は、最小のノード「2」をスタックに入れてアクセス処理を行う.
  • [Step 3]スタックの最上位ノード「2」である隣接ノード「7」がアクセスされていない.
    したがって、アクセス処理のためにスタックに「7」ノードを入れてください.
  • [Step 4]スタックの最上位ノード「7」には、アクセスされていない隣接ノード「6」および「8」がある.
  • は、最小のノード「6」をスタックに入れてアクセス処理を行う.
  • [Step 5]スタックの最上位ノード「6」には、アクセスされていない隣接ノードはありません.
    したがって、
  • はスタックから「6」ノードを取り出す.

  • 隣接ノード「8」が
  • [Step 6]スタックの最上位ノード「7」にアクセスしていない.
    したがって、アクセス処理のためにスタックに8番ノードを入れてください.

  • この手順を繰り返すと、ノード全体の参照順序(スタックに入る順序)は次のようになります.
    ナビゲーション順序:1->2->7->6->8->3->4->5
    ソースコード
    let graph = [
      [],        //0번노드는 주로 없는경우가 많아서 이렇게 비어있는 칸으로 두는경우가 많다.
      [2, 3, 8], //1번 노드에 연결된 간선들
      [1, 7],    //2번 노드에 연결된 간선들
      [1, 4, 5], //3번 노드에 연결된 간선들
      [3, 5],    //4번 노드에 연결된 간선들
      [3, 4],    //5번 노드에 연결된 간선들
      [7],       //6번 노드에 연결된 간선들
      [2, 6, 8], //7번 노드에 연결된 간선들
      [1, 7]     //8번 노드에 연결된 간선들
    ]
    
    let visited = Array(9).fill(false) 
    // 마찬가지로 0번 인덱스를 쓰지않으면 
    // 노드번호와 인덱스번호를 일치시킬수 있으므로 직관적으로 코딩이 가능하다.
    
    function dfs(graph, v, visited) {
      // 현재 노드를 방문 처리
      visited[v] = true;
      console.log(v)
      // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
      for(let index in graph[v]) {
        if(!visited[graph[v][index]]) {  // 이부분 코드 주의.. python이랑 달라서 고치는데 힘들었다.
          //방문했다면 true 안했다면 false 인데 거기에 not
          dfs(graph, graph[v][index], visited)
        }
      }
        
    }
    
    
    dfs(graph, 1, visited)
    

    BFS


    更新