webdevqa.jp.net

どのデータ構造がDFSとBFSで使用されているかをどのように思い出せますか?

スタックを使用するか、DFSまたはBFSのキューを使用するかは常に混同します。誰かがどのアルゴリズムがどのデータ構造を使用しているかを覚える方法についての直感を教えてください。

25
captcadaver

紙に小さなグラフを描き、各実装でノードが処理される順序を考えます。ノードに遭遇する順序とノードを処理する順序は、検索ごとにどのように異なりますか?

そのうちの1つはスタック(深さ優先)を使用し、もう1つはキュー(幅優先)を使用します(少なくとも非再帰的な実装の場合)。

25
James McNellis

Queueは、一般的にhorizo​​ntal構造と考えることができます。つまり、breadth/widthはそれに起因します-[〜#〜] bfs [〜#〜]

Stackvertical構造として視覚化されるため、depth-[〜#〜] dfs [〜#〜] =。

69

BFSは最初に最も近い頂点を探索/処理し、次にソースから外側に移動します。この場合、クエリを実行すると、挿入された順序に基づいて最も古い要素を提供するデータ構造を使用します。キューは先入れ先出し(FIFO)であるため、この場合に必要なものです。一方、DFSは各ブランチに沿って可能な限り最初に探索し、次にトラックトラックを探索します。このため、LIFO(last-in-first-out)であるため、スタックの動作が改善されます。

26
Lizz In

バーベキューを心に留めて覚えています。バーベキューは「B」で始まり、「q」のような音で終わるため、BFS-> Queueおよび残りのものはDFS->スタックです。

25
kawadhiya21

アルファベット順でそれを取ります...

.... B(BFS)..... C ...... D(DFS)....

.... Q(キュー)... R ...... S(スタック)...

6

BFSは常にキューを使用し、DFSはスタックデータ構造を使用します。前の説明でDFSがバックトラッキングを使用していることを伝えています。バックトラッキングはスタックによってのみ続行できることを忘れないでください。

5
ashutosh

深さ優先検索では、Stackを使用して、行き止まりに達したときにどこに行くべきかを記憶します。

DFSS

2

Bfs; Breadth => queue

DFS; Depth =>スタック

それらの構造を参照してください

2
Subrato
  1. スタック(Last In First Out、LIFO)。 DFSの場合、ルートから可能な限り最も遠いノードまで取得します。これはLIFOと同じ考えです。

  2. キュー(先入れ先出し、FIFO)。 BFSの場合、ノードの上位レベルにアクセスした後、ノードの下位レベルにアクセスした後、1レベルごとにそれを取得します。これはFIFOと同じ考え方です。

1

何も覚えていない。

検索に使用されるデータ構造が[〜#〜] x [〜#〜]であると仮定します。

幅優先 =入力されたノード[〜#〜] x [〜#〜]前、最初にツリーで生成する必要があります:Xはキューです。

Depth First =入力されたノード[〜#〜] x [〜#〜]後で、最初にツリーで生成する必要があります:Xはスタックです。

簡単に言うと、スタックは後入れ先出し、つまりDFSです。キューは先入れ先出し、つまりBFSです。

1
M-J

特に若い学生にとって覚えやすい簡単な方法は、同様の頭字語を使用することです:

BFS =>キューのBoy FriendS(人気のある女性向け)。

それ以外の場合、DFSは(スタック)です。

1
Hongyu Zhang

あなたは頭字語を作ることによって覚えることができます

[〜#〜] bqds [〜#〜]

美しい女王には罪があります。

ヒンディー語では、हुरानीक्युर्दहा

0

私はこの答えを共有したいと思います: https://stackoverflow.com/a/20429574/32216

BFSを使用してキューをスタックに置き換えると、DFSの同じ訪問順序が再現され、実際のDFSアルゴリズムよりも多くのスペースが使用されます。

0
arboreal84