[解決済み】広さ優先と深さ優先の比較

質問

ツリー/グラフをトラバースするとき、Breadth FirstとDepth Firstの違いは何ですか？コーディングや擬似コードの例があれば、教えてください。

どのように解決するのですか？

この2つの用語は、木の歩き方を2種類に分けて説明しています。

その違いを示すのが一番簡単だろう。木を考えてみましょう。

    A
   / \
  B   C
 /   / \
D   E   F

A 深さ 最初の探索では、次の順序でノードを訪問します。

A, B, D, C, E, F

わざわざ行くことに気づく 下 片足だけ

A 幅 最初の探索では、次の順序でノードを訪問します。

A, B, C, D, E, F

ここでは、すべての作業を行う 横断 の各レベルで、下に行く前に

(トラバーサルの順序に曖昧さがあることに注意し、各レベルのツリーで "read"の順序を維持するためにごまかしをしました。どちらの場合でも、私は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" 行を使用する）、そうではなく も 明示的なスタックを使うと大変なことになりますが、練習として残しておきます。