[algorithm] なぜDFSで、グラフでサイクルを見つけるためのBFSではないのですか?



2 Answers

  1. DFSは実装が簡単です
  2. DFSがサイクルを検出すると、スタックにはサイクルを形成するノードが含まれます。 同じことはBFSには当てはまりませんので、見つかったサイクルも印刷したい場合は余分な作業が必要です。 これにより、DFSがより便利になります。
Question

主にDFSは、BFSではなくグラフでサイクルを見つけるために使用されます。 何か理由は? ツリー/グラフを横切ってノードが既に訪問されているかどうかを見つけることができます。




ツリー内の任意の場所にサイクルを配置すると、DFSはツリーの約半分に覆われたサイクルをヒットする傾向があり、サイクルの進行する場所の半分の時間と、木の残りの半分に平均でそれを見つけるだろう)ので、それは約0.5 * 0.5 + 0.5 * 0.75 = 0.625という平均値で評価されます。

ツリー内の任意の場所にサイクルを配置すると、BFSはその深さにあるツリーのレイヤーを評価したときにのみサイクルをヒットする傾向があります。 したがって、通常、残高のバイナリツリーの葉を評価する必要があります。これにより、一般的にはツリーの評価が増えます。 特に、時間の3/4のうち、少なくとも2つのリンクの1つがツリーの葉に現れます。その場合、ツリーの平均3/4(リンクが1つある場合)または7 /あなたがすでに1/2 * 3/4 + 1/4 * 7/8 =(7 + 12)/ 32 = 21/32 = 0.656 ...というように、ツリーを探索するコストを追加することなく、葉ノードからサイクルを追加しなくてもよい。

さらに、DFSはBFSより実装が容易です。 したがって、あなたのサイクルについて何かを知っていなければ(例えば、サイクルがあなたが検索したルートの近くにある可能性が高い、BFSが利点を与えるような場合など)、使用しないでください。




グラフが周期的であることを証明するには、1サイクル(エッジが直接的または間接的に指向するエッジ)を持つことを証明する必要があります。

DFSでは、一度に1つの頂点を取り、サイクルがあるかどうかをチェックします。 サイクルが見つかるとすぐに、他の頂点のチェックを省略することができます。

BFSでは、多くの頂点のエッジを同時に追跡する必要があります。最後には、サイクルがあるかどうかを確認するよりも頻繁に追跡する必要があります。 グラフのサイズが大きくなるにつれて、BFSはDFSと比較してより多くの空間、計算、および時間を必要とする。




Related