質問

ツリー/グラフを走査するとき、幅優先と深さ優先の違いは何ですか?コーディングまたは疑似コードのサンプルは何でも構いません。

役に立ちましたか？

解決

これら 2 つの用語は、木の歩き方の 2 つの異なる方法を区別します。

おそらく違いを示すだけが最も簡単です。次のツリーについて考えてみましょう。

    A
   / \
  B   C
 /   / \
D   E   F

あ 深さ 最初の走査ではこの順序でノードを訪問します

A, B, D, C, E, F

ずっと進んでいることに気づいてください 下 次に進む前に片足。

あ 幅 最初の走査ではこの順序でノードを訪問します

A, B, C, D, E, F

ここで私たちはずっと働きます 横切って 下がる前の各レベル。

(走査順序には多少のあいまいさがあり、ツリーの各レベルで「読み取り」順序を維持するために不正行為を行っていることに注意してください。どちらの場合でも、C の前後で B に到達することができ、同様に F の前後で E に到達することができました。これはアプリケーションによって異なりますが、重要な場合もあればそうでない場合もあります...)

どちらの種類のトラバーサルも、次の疑似コードを使用して実現できます。

Store the root node in Container
While (there are nodes in Container)
   N = Get the "next" node from Container
   Store all the children of N in Container
   Do some work on N

2 つの走査順序の違いは、次の選択にあります。 Container.

  • のために 深さ優先 スタックを使用します。(再帰的な実装ではコールスタックを使用します...)
  • のために 幅優先 キューを使用します。

再帰的な実装は次のようになります

ProcessNode(Node)
   Work on the payload Node
   Foreach child of Node
      ProcessNode(child)
   /* Alternate time to work on the payload Node (see below) */

再帰は、子供がいないノードに到達すると終了するため、有限の非環式グラフで終了することが保証されます。

この時点では、まだ少し騙されています。少し賢くすれば、こんなこともできます 作業中 ノードは次の順序で配置されます。

D, B, E, F, C, A

これは深さ優先のバリエーションで、ツリーを上に戻るまで各ノードで作業を行いません。しかし、私は持っています 訪れた 上位のノードは、その子を見つけるために下降する途中にあります。

この走査は、再帰的実装 (最初の "Work" 行の代わりに上記の "Alternate time" 行を使用) では非常に自然であり、そうではありません。 あまりにも 明示的なスタックを使用する場合は難しいですが、練習として残しておきます。

他のヒント

用語の理解:

この図を見ると、その単語がどのような文脈で使われているかがわかるはずです。 幅 そして 深さ 使用されています。

Understanding Breadth and Depth

深さ優先検索:

Depth-First Search

  • 深さ優先の探索アルゴリズムは、あたかも遠くまで行きたいかのように動作します スタート地点からできるだけ早く。

  • 一般的には、 Stack 行き止まりに達したときにどこに行くべきかを覚えておくためです。

  • 従うべきルール:最初の頂点 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 つを選択できます。それぞれの選択はさらなる選択肢につながり、それぞれの選択肢はさらにさらなる選択肢につながり、というように、可能性のツリー状のグラフが拡大し続けます。

幅優先検索:

Breadth-First Search

  • 幅優先の検索アルゴリズムは、できるだけ近くにとどまることを好みます 出発点に向かいます。
  • この種の検索は通常、 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 による優れたデータ構造の本の「グラフ」の章をお勧めします。

この二分木があるとします。

enter image description here

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

「私は 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

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

次の 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 の簡単な説明がとても気に入りました。
「In-Order Traversal は [BST (二分探索木) の順序で] 値を出力します。」
「事前順序トラバーサルは、[二分探索ツリー] のコピーを作成するために使用されます。」
「ポストオーダートラバーサルは[二分探索木]を削除するために使用されます。」
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing

私はそれが思わとして、あなたがあなたのdillemaがそれほど強くないことがわかりますように、コードのみのいくつかの行を切り替えることによって、あなたに1つのアルゴリズムまたは他のを与えるだろう方法でそれらの両方を記述するために興味深いものになるだろうと思います最初であること。

I個人風景をフラッディングとしてBFSの解釈のような低高度領域が最初に浸水され、のみ、高高度領域が続くであろう。我々は地理の本で見るように、あなたは、これは物理学とあるのと同じように、BFSが同時に同じ孤立線の下にあるすべてのエリアを埋めることを見てその簡単な、等値線として風景の高度を想像した場合。このように、距離や拡大縮小、コストと高度を解釈することは、アルゴリズムのかなり直感的なアイデアを提供します。

このことを念頭に、あなたは簡単に広がりやすい最小全域木を見つけるための最初の検索、最短経路、および他の多くの最小化アルゴリズムの背後にある考え方を適応させることができます。

私はまだ（迷路についてのみ、標準の一つが、それはBFS 1や洪水のように強力なイマイチ）DFSのいずれかの直感的な解釈を参照してくださいdidntの私にとって、説明したようBFSは、物理現象とのより良い相関すると思われるようですので、上記、DFSは、合理的なシステム上での選択肢のdillemaとのより良い相関している間（すなわちチェスゲームに作るために移動したり、迷路から出て行く人や決定コンピュータ）。

だから、私にとって自然現象のベストは、実際の生活の中で彼らの伝搬モデルを（横断）と一致した上で嘘の違います。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top