コードは必要ありません。説明だけで十分です。教科書にはこう書いてあります
レベル順序: レベル i の各ノードは、レベル i+1 のどのノードよりも先に処理されます。
幅優先探索とは、ルートに最も近いノードを左から探索する、という理解ですが、これはどう違うのでしょうか? これは正方形や長方形のような状況でしょうか?
ベストアンサー1
「適切な」ツリー(下記参照)の場合、少なくともほとんどの定義では同じです。ウィキペディア、 例えば:
幅優先
参照: 幅優先探索
木々を横断することもできるレベル順、...
... 幅優先 (レベル順) のトラバーサル ...
まあ、少なくともレベル順の走査は幅優先走査と同じであるトラバーサル何かを横断する理由は様々であり、幅優先探索のように検索するだけではありません。検索多くの人(またはほとんど)は、その区別をせず、これらの用語を互換的に使用していますが、そのように暗示されているようです。
私が個人的に「レベル順トラバーサル」を使うのは、順序順、順序後、順序前のトラバーサル、同じ「... 順序のトラバーサル」形式に従うだけです。
一般的なグラフでは、「レベル」という概念は適切に形成されていない可能性があります(ただし、できたおそらく、ソース ノードからの (最短の) 距離として定義するだけなので、レベル順のトラバーサルは明確に定義されていない可能性がありますが、幅優先検索は依然として完全に理にかなっています。
上で「適切な」ツリーについて言及しました (ご存じかもしれませんが、これは完全に作り話のサブ分類です)。これは単に「レベル」が予想どおりに定義されていることを意味します。つまり、各エッジによってレベルが 1 つずつ増加します。ただし、「レベル」の定義を少し変更することはできます (ただし、これを行うことは広く受け入れられない可能性があります)。つまり、エッジがレベルを飛び越えること (または同じレベルのノード間にエッジがあること) が可能になります。たとえば、次のようになります。
level
1 1
/ \
2 / 3
/ /
3 2 4
したがって、レベル順のトラバーサルは となり1, 3, 2, 4
、
幅優先のトラバーサルは となります1, 2, 3, 4
。