問題タブ [breadth-first-search]

私が覚えてチェックしたように、ツリーをトラバースしたり、Web 幅優先 (BFS) をクロールしたりする通常の方法は、キューを使用することです。実際にキューを使用せずに実装する方法はありますか?

各ノードが値を持つことができる二分木があります。

ツリー内で値がnullで、ルートに最も近いノードを見つけたいと思います。ルートから同じ距離にある2つのノードがある場合は、どちらでもかまいません。二分木への読み取りアクセスの数を最小限に抑える必要があります。作業メモリーがkノードのみに制限されていると想定します。

深さkまでのDFSは網羅的ですが、最初にツリー全体を実行しない限り、最も近いノードは見つかりません。BFSは最も近いものを見つけますが、DFSは同じメモリでより深いヌルを見つけることができるため、失敗する可能性があります。

ツリーへの読み取りアクセスの数を最小限に抑えて、最も近いnullノードを見つけたいと思います。

（最終的にはこれをn-wayツリーにも実装する必要があるため、一般的な解決策が適切です。ツリーへの書き込みアクセスはなく、読み取りのみです。）

これはインタビューの質問です

解決策を考えます。キューを使用します。

キューを使用しない、これよりも優れたソリューションを考えられるものはありますか?

Javaを使ってDFS(深さ優先探索)とBFSを実装したいです。

Javaには、すぐに使用できる組み込みのツリーデータ構造がありますか? または私が使用できる他のものはありますか？

基準を満たすノードが見つかったので、検索を停止する必要があるとします。

私の本には、幅優先検索用の次の疑似コードがあります。

これらの疑似コードの指示に従って、同様のアルゴリズムを自分で実装しました。私の質問は、ソリューション パスを維持するように変更する最も簡単な方法は何ですか?

解決策にたどり着くことができるということを単純に知ることは、解決策にたどり着くまでの遷移のリストを持つことほど役に立ちません。

重み付けされていないグラフで、あるノードから別のノードへの最短経路を返すメソッドを作成しようとしています。ダイクストラ法の使用を検討しましたが、ペアが1つしかないので、これは少しやり過ぎのようです。代わりに幅優先探索を実装しましたが、問題は、返されるリストに不要なノードが含まれていることです。目標を達成するためにコードを変更するにはどうすればよいですか？

ツリー構造で幅優先検索と A* を使用する方法は理解していますが、次のグラフが与えられた場合、どのように実装されますか? 言い換えれば、検索はどのようにグラフを横断するのでしょうか? S は開始状態です

グラフはこちら

私はinotifyを利用してファイルアクセスを監視するデーモンを書いていますが、再帰検索で何も見逃さないことが重要です。私はこの興味深いアイデアを見つけ、それを実装し始めました。

ftw（）およびftw64（）は、幅優先アルゴリズムを使用せず、より「事前注文」します。nftw（）には深さ優先のオプションがありますが、上葉のレースが心配です。

何か、おそらくGNU拡張機能が不足していることを望んでいますか？それとも、タイプセーフなコールバックを使用して独自のコールバックを実装することを検討しているだけですか（実際には実行したくないことです）。

または、このタイプのアプリケーションでは、幅優先探索と深さ優先探索の利点についての私の理解は誤りですか？

通常、グラフをたどる必要があるときは、空間の複雑さが低いため、常に深さ優先検索を使用してきました。私の経験はかなり限られていますが、正直なところ、幅優先検索が必要な状況を見たことがありません。

幅優先検索を使用する意味があるのはいつですか?

更新：ここでの私の答えは、BFSを使用した状況を示していると思います（DFSだと思っていたため）。この場合、なぜそれが役に立ったのか、私はまだ知りたいと思っています。