algorithm - 幅優先と深さ優先

Question

ツリー/グラフをトラバースするとき、幅優先と深さ優先の違いは何ですか? コーディングや疑似コードの例はどれも素晴らしいでしょう。

Answer 1

用語を理解する:

この図は、幅と深さという言葉が使用されている文脈についてのアイデアを提供するはずです.

---

深さ優先検索:

• 深さ優先検索アルゴリズムは、開始点からできるだけ早く離れたいかのように機能します。

• 通常Stack、行き止まりに達したときにどこに行くべきかを記憶するために a を使用します。

• 従うべきルール: 最初の頂点 A をStack

  1. 可能であれば、隣接する未訪問の頂点を訪問し、訪問済みとしてマークし、スタックにプッシュします。
  2. ルール 1 に従えない場合は、可能であれば、スタックから頂点をポップします。
  3. ルール 1 またはルール 2 を守れない場合は、おしまいです。

• Java コード:

  public void searchDepthFirst() {
      // Begin at vertex 0 (A)
      vertexList[0].wasVisited = true;
      displayVertex(0);
      stack.push(0);
      while (!stack.isEmpty()) {
          int adjacentVertex = getAdjacentUnvisitedVertex(stack.peek());
          // If no such vertex
          if (adjacentVertex == -1) {
              stack.pop();
          } else {
              vertexList[adjacentVertex].wasVisited = true;
              // Do something
              stack.push(adjacentVertex);
          }
      }
      // Stack is empty, so we're done, reset flags
      for (int j = 0; j < nVerts; j++)
          vertexList[j].wasVisited = false;
  }
  

• アプリケーション: 深さ優先検索は、ゲームのシミュレーション (および現実世界のゲームのような状況) でよく使用されます。典型的なゲームでは、いくつかの可能なアクションから 1 つを選択できます。それぞれの選択肢はさらなる選択肢につながり、それぞれの選択肢はさらなる選択肢につながり、さらに拡大し続ける可能性のツリー形状のグラフになります。

---

幅優先検索:

• 幅優先探索アルゴリズムは、開始点にできるだけ近いところにとどまることを好みます。
• この種の検索は、通常、 を使用して実装されQueueます。
• 従うべきルール: 開始頂点 A を現在の頂点にする
  1. 現在の頂点に隣接する次の未訪問の頂点 (存在する場合) にアクセスし、それをマークして、キューに挿入します。
  2. 未訪問の頂点がなくなったためにルール 1 を実行できない場合は、(可能であれば) キューから頂点を削除し、それを現在の頂点にします。
  3. キューが空であるためにルール 2 を実行できない場合は、完了です。

• Java コード:

  public void searchBreadthFirst() {
      vertexList[0].wasVisited = true;
      displayVertex(0);
      queue.insert(0);
      int v2;
      while (!queue.isEmpty()) {
          int v1 = queue.remove();
          // Until it has no unvisited neighbors, get one
          while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {
              vertexList[v2].wasVisited = true;
              // Do something
              queue.insert(v2);
          }
      }
      // Queue is empty, so we're done, reset flags
      for (int j = 0; j < nVerts; j++) 
          vertexList[j].wasVisited = false;
  }
  

• アプリケーション: 幅優先探索では、最初に始点から 1 エッジ離れたすべての頂点が検出され、次に 2 エッジ離れたすべての頂点が検出されます。これは、開始頂点から特定の頂点までの最短パスを見つけようとしている場合に役立ちます。

うまくいけば、幅優先検索と深さ優先検索を理解するのに十分なはずです。さらに読むには、Robert Lafore による優れたデータ構造の本のグラフの章をお勧めします。

Answer 2

この二分木を考えると：

幅優先トラバーサル:
各レベルを左から右にトラバースします。

「私は G、私の子供は D と私、私の孫は B、E、H、K、孫は A、C、F です」

- Level 1: G 
- Level 2: D, I 
- Level 3: B, E, H, K 
- Level 4: A, C, F

Order Searched: G, D, I, B, E, H, K, A, C, F

深さ優先トラバーサル:
トラバーサルは一度にレベル全体にわたって行われません。代わりに、トラバーサルは最初にツリーの DEPTH (ルートからリーフまで) に飛び込みます。ただし、単純な上下よりも少し複雑です。

次の 3 つの方法があります。

1) PREORDER: ROOT, LEFT, RIGHT.
You need to think of this as a recursive process:  
Grab the Root. (G)  
Then Check the Left. (It's a tree)  
Grab the Root of the Left. (D)  
Then Check the Left of D. (It's a tree)  
Grab the Root of the Left (B)  
Then Check the Left of B. (A)  
Check the Right of B. (C, and it's a leaf node. Finish B tree. Continue D tree)  
Check the Right of D. (It's a tree)  
Grab the Root. (E)  
Check the Left of E. (Nothing)  
Check the Right of E. (F, Finish D Tree. Move back to G Tree)  
Check the Right of G. (It's a tree)  
Grab the Root of I Tree. (I)  
Check the Left. (H, it's a leaf.)  
Check the Right. (K, it's a leaf. Finish G tree)  
DONE: G, D, B, A, C, E, F, I, H, K  

2) INORDER: LEFT, ROOT, RIGHT
Where the root is "in" or between the left and right child node.  
Check the Left of the G Tree. (It's a D Tree)  
Check the Left of the D Tree. (It's a B Tree)  
Check the Left of the B Tree. (A)  
Check the Root of the B Tree (B)  
Check the Right of the B Tree (C, finished B Tree!)  
Check the Right of the D Tree (It's a E Tree)  
Check the Left of the E Tree. (Nothing)  
Check the Right of the E Tree. (F, it's a leaf. Finish E Tree. Finish D Tree)...  
Onwards until...   
DONE: A, B, C, D, E, F, G, H, I, K  

3) POSTORDER: 
LEFT, RIGHT, ROOT  
DONE: A, C, B, F, E, D, H, K, I, G

使用法 (別名、なぜ気にする必要があるのか​​):
深さ優先トラバーサル メソッドとそれらが一般的にどのように使用されるかについてのこの簡単な Quora の説明を本当に楽しんだ
: "
"[二分探索木] のコピーを作成するために、プレオーダー トラバーサルが使用されます。"
「[二分探索木] を削除するためにポストオーダー トラバーサルが使用されます。」
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing

Answer 3

コードのいくつかの行を切り替えるだけでどちらかのアルゴリズムが得られるような方法で両方を書くと面白いと思います。 .

私は個人的には、BFS をランドスケープを氾濫させるものとして解釈するのが好きです。つまり、まず標高の低い地域が浸水し、その後に標高の高い地域がそれに続くということです。地形の高度を地理学の本で見られるように等高線として想像すると、BFS が同じ等高線の下のすべての領域を同時に塗りつぶすことが容易にわかります。これは物理学の場合と同じです。したがって、高度を距離またはスケーリングされたコストとして解釈すると、アルゴリズムの非常に直感的なアイデアが得られます。

これを念頭に置いて、幅優先検索の背後にあるアイデアを簡単に適応させて、最小スパニング ツリー、最短パス、および他の多くの最小化アルゴリズムを簡単に見つけることができます。

私はまだ DFS の直感的な解釈を見ていません (迷路に関する標準的なものだけですが、BFS やフラッディングほど強力ではありません)。 DFS は、合理的なシステムでの選択肢のジレマ (つまり、チェス ゲームでどちらを動かすか、または迷路から出るかを決定する人またはコンピューター) とよりよく相関します。

したがって、私にとっては、どの自然現象が現実の伝播モデル (横断) に最もよく一致するかという嘘の違いです。