webdevqa.jp.net

幅優先検索とレベル順トラバーサルの違いは何ですか?

コードは必要ありません。説明だけです。私の教科書には

レベルの順序:レベルiの各ノードは、レベルi +1のノードの前に処理されます。

幅優先探索についての私の理解は、左から始めて、最初にルートに最も近いノードを探索するということですか?これはどう違うのですか?これは正方形と長方形のような状況ですか?

23
munchschair

「適切な」ツリー(以下を参照)の場合、少なくともほとんどの定義では同じです。のように ウィキペディア 、例:

幅優先

参照:幅優先探索

ツリーは、level-order、..でトラバースすることもできます。

...幅優先(レベル順)走査.。

まあ、少なくともレベル順のトラバーサルは幅優先トラバーサルと同じです。何かをトラバースする理由はたくさんありますが、幅優先searchが示唆しているように、多くの(またはほとんどの場合)その区別を行わず、用語を交換可能に使用します。

私が個人的に「レベル順トラバーサル」を実際に使用するのは、同じ「...-順序トラバーサル」に従うためだけに、 インオーダートラバーサル、ポストオーダートラバーサル、プレオーダートラバーサル について話すときだけです。フォーマット。


一般的なグラフの場合、「レベル」の概念は整形式ではない可能性があります(ただし、couldソースノードからの(最短)距離として定義するだけです)。したがって、レベル-順序トラバーサルは明確に定義されていない可能性がありますが、幅優先探索は依然として完全に理にかなっています。

上記の「適切な」ツリーについて言及しました(これは、疑問に思った場合に備えて、完全にサブ分類で構成されています)。これは、単に「レベル」が期待どおりに定義されていることを意味します。各エッジのレベルが1つずつ増加します。ただし、「レベル」の定義を少し試してみることもできます(ただし、これは広く受け入れられていない場合があります)。本質的に、エッジがレベルを飛び越えることを許可します(または同じレベルのノード間にエッジがある場合もあります)。例えば:

level
  1          1
            / \
  2        /   3
          /   /
  3      2   4

したがって、レベル順のトラバーサルは1, 3, 2, 4になります。
幅優先探索は1, 2, 3, 4になります。

20
Dukeling

ツリーにはレベル順トラバーサルを使用します。これは、ツリーにはサイクルがなく、ノードにアクセスすると、ノードに再度アクセスすることはありませんが、グラフではそうではないためです。グラフも周期的である可能性があり、グラフが周期的である場合、ノードが訪問された場合のレベルの順序に従って、ノードが訪問されたかどうかをチェックせず、同じノードを無限にトラバースします。プログラムはサイクルのためにトラバースし続けます。したがって、グラフの場合はBFSまたはDFSを使用します。

0
SUMIT LOHAN