私は、London Undergroundを検索するためのBreadth-Firstグラフ検索アルゴリズムを構築中です。Breadth-Firstアルゴリズムを効率的に実装するための動的キュー
私はアルゴリズムを理解しましたが、あなたがよく知っているように、アルゴリズムは正しい順序で検索する必要があるすべてのエッジを追跡するためにキューADSを必要とします。
私は、キューの管理やキューに入れられたアイテム（エッジ）の数が非常に多い、あるいは非常に多いという効率に関する問題について読んできました。
Java ArrayListに基づいてキューを実装する方法を教えてください。ヘッドとテールを追跡でき、成長中のメモリを効果的に管理できますか？
どのようなヒント/ポインタがありがとう！
私はあなたの質問が密接にこのトピックに関連していると思う：あなたは本当に正当な理由がない限りBreadth-First search in Java
は、ArrayListを使用しないでください。 Javaにはすでにキュー実装が用意されています。詳細はQueueインターフェイスを参照してください。
場合によっては、LinkedListをキューの実装として選択するだけで十分です。 LinkedListをキューとして使用する幅広い最初の検索実装の例を簡単に説明します。http://www.codeproject.com/KB/java/BFSDFS.aspxも参照してください。
あなたのオブジェクトがすでにキューに入っているかどうかを高速にテストしたい場合は、注意してください。 ArrayListもQueueもこの機能を提供しません（containsのチェックはO(n)です）。余分なフィールドを追加することによって対処しているオブジェクトを変更することができれば、簡単です。そうでない場合は、どのオブジェクトがキューに入っているかを把握するために、ある種の高速のSet（おそらくHashSet）を維持したいでしょう。
私が最初に尋ねることは、あなたが実際に問題を抱えていることです。それはあなたを待っていますか？ 2つ目は、あなたが待っている場合は、それがほとんどの時間を費やしているかを見るためにサンプリングしています。そのFIFOは問題になるかもしれませんが、おそらく先験的ではありません。野球場の推測と同様に、1マイクロ秒ごとに1つのノードを処理できるはずなので、スピードが問題になるとは思わないでしょう。 –
私はいつも私のキューを並べ替えるよりもベターですので、私はむしろ何らかの特殊キューを使用したいと思います。それを行うことは不可欠ではありませんが、私は単に待ち行列とそれらがどのようにできるかについてもっと知りたいと思います。 – Alex
私はあなたがなぜソートする必要があるのか分かりませんが、とにかく@金さんの答えはよさそうです。 –