データ構造とアルゴリズムシリーズ - 深さ優先と幅優先

序文

データ構造とアルゴリズムシリーズ（完了部分）:

時間計算量と空間計算量の分析
配列の基本的な実装と特徴
リンクリストとジャンプリストの基本的な実装と特徴
スタック、キュー、優先キュー、両端キューの実装と特性
ハッシュテーブル、マップ、セットの実装と特性
木、二分木、二分探索木の実装と特徴
ヒープとバイナリヒープの実装と特徴
グラフの実装と機能
再帰の実装、特徴、重要なポイント
分割統治とバックトラッキングの実装と特徴
深さ優先探索と幅優先探索の実装と特徴
貪欲アルゴリズムの実装と特徴
二分探索の実装と特徴
動的計画法の実装とポイント
タイヤツリーの基本的な実装と特徴
union-findの基本的な実装と特徴
剪定の実装と特徴
双方向BFSの実装と特徴
ヒューリスティック探索の実装と特徴
AVL木と赤黒木の実装と特徴
ビット演算の基礎と実践ポイント
ブルームフィルタの実装と応用
LRUキャッシュの実装と応用
初級ソートと上級ソートの実装と特徴
文字列演算

PS: 公式アカウントやGitHubではほとんど完成しており、後日Toutiaoにリンクが追加されます（外部リンクは許可されていません）

この記事では、深さ優先探索と幅優先探索について説明します。

検索とトラバーサルについて

検索に関しては、ほとんどの場合、いわゆる「総当たり検索」、つまり比較的単純で素朴な検索を扱います。つまり、検索するときには、いわゆるインテリジェントな状況は考慮されません。多くの場合、すべてのノードを 1 回走査して、必要な結果を見つけるという 1 つのことが行われます。

このようなデータ構造に基づいて、データ構造自体に何らかの特徴がない場合、つまり、それはごく普通のツリーまたはごく普通のグラフです。次に、すべてのノードをトラバースする必要があります。同時に、各ポイントが 1 回だけ訪問され、最終的に結果が見つかるようにします。

そこで、まず検索全体を簡略化し、次にツリーの状況に合わせて縮小してみましょう。

必要な値を見つけたい場合、このツリーで何をすればよいでしょうか?そうすると、ルートから始めて、まず左のサブツリーを検索し、次に次のポイントに 1 つずつ進み、終了したら右のサブツリーに進み、目的のポイントが見つかるまで続ける必要があることは間違いありません。これが私たちが使用する方法です。

データ構造の定義に戻ると、左サブツリーと右サブツリーだけがあります。

このようなトラバーサルや検索を実装したい場合、次の点を確実にする必要があります。

各ノードは1回ずつ訪問する必要がある
各ノードは一度だけ訪問される
ノードアクセスの順序に制限はありません
深さ優先探索
幅優先探索

一度だけ訪問するということは、検索中に無駄な訪問をあまり行わないことを意味します。そうしないと、アクセス効率が非常に低下します。

もちろん、他の検索も可能であり、他の検索は深さ優先や幅優先ではなく、優先度優先になります。もちろん、途中から他のものを優先するなど、任意に定義することもできますが、その定義は実際のシナリオに基づいている必要があります。したがって、一般的には深さ優先、幅優先、優先度優先と考えることができます。優先順位による検索は、実際には多くのビジネスシナリオに適しています。このアルゴリズムは一般にヒューリスティック検索と呼ばれ、ディープラーニングの分野でよく使用されます。このような優先順位は、例えば、さまざまな推奨アルゴリズムや高度な検索アルゴリズムでよく使用され、ユーザーが最も関心のあるコンテンツを検索できるようにしたり、毎日DouyinやKuaishouを開いたときに最も関心のあるコンテンツを推奨したりするのが、実はその理由です。

深さ優先探索 (DFS)

再帰的な記述

再帰書き込み方式は、再帰の終了条件から開始し、現在のレイヤーを処理してから次に進みます。

次に、現在のレイヤーを処理することは、ノード node を訪問し、このノード node を訪問済みノードに追加するのと同じです。
終了条件は、このノードが以前に訪問されたことがあるかどうかは関係ないということです。
次に、下に行くと、その子ノードに移動します。バイナリツリーの場合は、左の子と右の子です。グラフの場合は、隣接するノードです。マルチブランチツリーの場合は、子です。次に、すべての子を 1 回トラバースします。

1. バイナリツリーテンプレート

Javaバージョン

//C/C++
 //再帰的な書き込み:
 map< int , int > を訪問しました。 
 
 void dfs(ノード*ルート) {
  //ターミネータ
  if (!root)戻り値; 
 
  if (訪問回数( ルート->val) ) {
    // すでに訪問済み
戻る;
  } 
 
  訪問[root->val] = 1; 
 
  // ここで現在のノードを処理します。
  // ...
 ( int i = 0 ; i < root->children.size ( ); ++i) {
    dfs(ルート->子[i]);
  }
戻る;
 }

Python バージョン

#パイソン
訪問 =設定() 
 
 def dfs(ノード、訪問済み):
    ノードが訪問済みの場合: # ターミネータ
        # すでに訪問済み
戻る   
 
    訪問しました。追加（ノード） 
 
    # ここで現在のノードを処理します。
    ...
 node.children()内のnext_nodeの場合:
        next_nodeが 訪問した場所:
            dfs(次のノード、訪問済み)

C/C++ バージョン

//C/C++
 //再帰的な書き込み:
 map< int , int > を訪問しました。 
 
 void dfs(ノード*ルート) {
  //ターミネータ
  if (!root)戻り値; 
 
  if (訪問回数( ルート->val) ) {
    // すでに訪問済み
戻る;
  } 
 
  訪問[root->val] = 1; 
 
  // ここで現在のノードを処理します。
  // ...
 ( int i = 0 ; i < root->children.size ( ); ++i) {
    dfs(ルート->子[i]);
  }
戻る;
 }

JavaScript バージョン

訪問 =設定()
 def dfs(ノード、訪問済み):
    ノードが訪問済みの場合: # ターミネータ
        # すでに訪問済み
戻る  
    訪問しました。追加（ノード）
    # ここで現在のノードを処理します。
    ...
 node.children()内のnext_nodeの場合:
      next_nodeが 訪問した場所:
        dfs(次のノード、訪問済み)

2. マルチブランチツリーテンプレート

訪問 =設定()
 def dfs(ノード、訪問済み):
    ノードが訪問済みの場合: # ターミネータ
        # すでに訪問済み
戻る  
    訪問しました。追加（ノード）
    # ここで現在のノードを処理します。
    ...
 node.children()内のnext_nodeの場合:
      next_nodeが 訪問した場所:
        dfs(次のノード、訪問済み)

非再帰的な記述

Python バージョン

#パイソン
def DFS(自己、ツリー): 
 
    tree.rootがNone の場合:
戻る[] 
 
    訪問済み、スタック = []、[tree.root] 
 
    スタック中:
        ノード = stack.pop()
        訪問しました。追加（ノード） 
 
        プロセス（ノード）
        ノード = generate_related_nodes(ノード)
        スタック.push(ノード) 
 
    # その他の処理作業  
    ...

C/C++ バージョン

//C/C++
 //非再帰的な書き込み:
 void dfs(ノード*ルート) {
  map< int , int > を訪問しました。
  if(!root)戻り値; 
 
  スタック<Node*> stackNode;
  スタックノードをプッシュします(ルート); 
 
  スタックノードが空である間（！スタックノードが空である間）{
    ノード* ノード = stackNode.top ();
    スタックノードをポップします。
    if (visited.count (node->val) )継続;
    訪問[node->val] = 1; 
 
 
 ( int i = node->children.size ( ) - 1; i >= 0; --i) {  
        ノードをスタックします。
    }
  } 
 
戻る;
 }

トラバーサル順序

深さ優先探索または深さ優先トラバーサルを見ると、トラバーサルの順序全体が常にルートノード 1 から始まることは間違いありません。次にどのブランチに進んでも、実際には同じです。簡単にするために、左端から開始します。したがって、深さ優先の場合は、最後まで進みます。

多分岐ツリーテンプレートを参考にして、頭の中で図を描いたり、そのような構造である再帰状態ツリーを再帰的に描いたりすることができます。

例えば、ルートを通り過ぎると、ルートはvisitedに最初に入れられ、ルートが訪問済みであることを示します。訪問された後、root.childernからnext_nodeを探します。そのnext_nodesはすべて訪問されていないので、最初に一番左のノードを訪問します。ここで、一番左のノードが最初に取り出された場合は、ルート以外のノードが訪問されていないため、visitedにないと判断されることに注意してください。そうでない場合は、直接dfsを呼び出し、next_nodeは一番左のノードを入れ、次にvisitedを一緒に入れます。
再帰呼び出しの特徴は、ループの実行が完了するのを待たずに、直接次のレイヤーに進むことです。つまり、現在の夢の場合、ここにループが書かれていますが、最初のループにあるときに、新しい夢のレイヤーにドリルダウンを開始します。

グラフ走査順序

幅優先探索 (BFS)

幅優先トラバーサルでは、再帰やスタックは使用されなくなり、いわゆるキューが使用されます。これは、水滴が位置 1 に落ち、その水の波紋が層ごとに広がっていく様子を想像してみてください。

両者の比較

BFS コードテンプレート

//Java
パブリッククラス TreeNode {
整数値;
    TreeNode左;
    TreeNode右; 
 
    ツリーノード( int x) {
        val = x;
    }
 } 
 
パブリックList<List< Integer >> levelOrder(TreeNode ルート) {
    List<List< Integer >> allResults = new ArrayList<>();
    ルートがnullの場合
すべての結果を返します。
    }
    Queue<TreeNode> ノード = new LinkedList<>();
    ノードを追加します(ルート);
    ノードが空の場合
整数 サイズ= nodes.size () ;
        List< Integer > 結果 = new ArrayList<>();
 ( int i = 0; i <サイズ; i++) {
            TreeNode ノード = nodes.poll();
            結果を追加します(node.val);
            （ノード.left != null ）の場合 {
                ノードを追加します(ノードの左)。
            }
            （ node.right != null ）の場合 {
                ノードを追加します(ノードの右)。
            }
        }
        allResults.add (結果);
    }
すべての結果を返します。
 }

パイソン
def BFS(グラフ、開始、終了):
    訪問 =設定()
    キュー = []
    キューに追加([開始])
    キュー中:
        ノード = キュー.pop()
        訪問しました。追加（ノード）
        プロセス(ノード)
        ノード = generate_related_nodes(ノード)
        キュー.push(ノード)
    # その他の処理作業  
    ...

 // C/C++
 void bfs(ノード*ルート) {
  map< int , int > を訪問しました。
  if(!root)戻り値; 
 
  キュー<Node*> queueNode;
  キューノードをプッシュします(ルート); 
 
  キューノードが空の場合（）{
    ノード* ノード = queueNode.top ();
    キューノードをポップします。
    if (visited.count (node->val) )継続;
    訪問[node->val] = 1; 
 
 ( int i = 0 ; i < node->children.size ( ); ++i) {
        queueNode.push(node->children[i]);
    }
  } 
 
戻る;
 }

 //JavaScript
 const bfs = (ルート) => {
  結果 = []、キュー = [ルート]
  （キューの長さ > 0）{
    レベル= []、n = キューの長さ
( i = 0; i < n; i++ とします) {
      ノードをキュー.pop() にします。
レベル.push(node.val)
      if ( node.left ) queue.unshift( node.left )
      if ( node.right ) キュー.unshift( node.right )
    }
    result.push(レベル)
  }
結果を返す
};