0

Java に触れてから長い時間が経っているので、これは奇妙な質問のように思えるかもしれません。現在、この幅優先検索コードを StackOverflow で見つけました。最後に変更しましたが、元のコードをここに投稿します。

public List<Node> getDirections(Node start, Node finish){
    List<Node> directions = new LinkedList<Node>();
    Queue<Node> q = new LinkedList<Node>();
    Node current = start;
    q.add(current);
    while(!q.isEmpty()){
        current = q.remove();
        directions.add(current);
        if (current.equals(finish)){
            break;
        }else{
            for(Node node : current.getOutNodes()){
                if(!q.contains(node)){
                        q.add(node);
                }
            }
        }
    }
    if (!current.equals(finish)){
        System.out.println("can't reach destination");
}
return directions;
}

私は他の深さ優先検索アルゴリズムを知っていますが、幅優先検索を深さ優先検索に簡単に変換できるとも言われました.2つのまったく異なるコードではなく、このコードに変換した方がよく理解できるでしょう. .

これを深さ優先検索に変更するにはどうすればよいですか?

4

4 に答える 4

5

深さ優先と幅拳の主な違いは、「フロンティア」(まだ探索していないノードのリスト) 内のノードを探索する順序です。

現在のノードからの出力ノードをそのリストの最後に追加すると、次のレベルに進む前に、「レベル」ですべての可能性をテストすることになります (簡単にするために、これをツリーとして想像してください)。幅優先検索を行います。

一方、以前に追加したノード (ツリーの「上位」レベルに属するノード) の前に、新しく追加されたノード (現在の位置からの発信ノード) を探索すると、次のようになります。最初に木の深さを調べます。

データ構造的には、キューではなくスタックが必要ですが、説明が役立つと思います。

于 2011-10-13T19:47:05.037 に答える
2

q.add(node)（リストの最後に追加する）を（最初に追加する）に置き換える必要がありますq.add(0, node)。基本的に、のstack代わりにを使用しqueueます。

明らかに、にアクセスするためのListインターフェイスではなく、インターフェイスを使用する必要があります。QueueLinkedList

于 2011-10-13T19:38:54.067 に答える
1 
Deque<Node> q = new LinkedList<Node>();

との代わりにとを使用popしますpushremoveadd

基本的に、追加したのと同じ側から削除します（通常remove、addLIFOキューの基本操作です）深さは最初にFIFOスタックを使用します

他の検索アルゴリズムは基本的に同じですが、異なるタイプのキューを使用します（たとえば、熱心な検索では最も簡単な次のステップを使用します）

于 2011-10-13T19:40:31.943 に答える
0

およびを、、、QueueおよびLinkedListで置き換えるStack_addpushremovepop

于 2011-10-13T19:44:24.263 に答える