0

2 つの文字列間の最短パスを見つけようとしており、実行されたステップ数の int を返します。String[]各文字列（キー）にその文字列の隣人をすべて含む（オブジェクト）があるHashMapがあるとします。

このコードは私が作成したものです。基本的な BFS を取得してコピーしようとしましたが、進行する方法がわかりません。

public class Main {
private static HashMap<String, String[]> list;

private static int makePath(String from, string to) {

    int path = 0;
    PriorityQueue<String> queue = new PriorityQueue<>();
    queue.add(from);

    while (!queue.isEmpty()) {
        String u = queue.poll();
        if (u == to) {
            return path;
        }
        else {
            for (String r : list.get(u)) {

               ...

            }
            return path;
        }
    }
    return 0;
}

}

これは、私の HashMap がどのように見えるかの単なる例です:

Goat, adj[] {Fish, Cow, Chicken}
Cow, adj[] {Pig, Pigeon}
Fish, adj[] {Goat, Bulbasaur, Dolphin, Eagle}

魚から牛まで、2 つのステップが必要です。魚からヤギへ、ヤギから魚へ。

ですから、何かアイデアがあれば、遠慮なく共有してください :)

4

1 に答える 1

0

2つのキューを使用することを考えています。fromword を firstQueue にエンキューし、 whilefirstQueueが空でない間、その隣人がまだ と等しくない場合、別のキューに隣人を格納する代替ロジックを実行しますto。

コードを教えて頂ければ分かりやすいかと思いますが、

private static int makePath(final HashMap<String, String[]> tree, final String from, final String to) {

        int path = 0;
        Queue<String> firstQueue = new PriorityQueue<>();
        Queue<String> secondQueue = new PriorityQueue<>();
        firstQueue.add(from);

        while (!firstQueue.isEmpty()) {
            String key = firstQueue.poll();
            String[] neighbors = tree.get(key);
            if (neighbors != null) {
                path++;
                for (String neighbor : neighbors) {
                    if (neighbor.equals(to)) {
                        return path;
                    } else {
                        secondQueue.add(neighbor);
                    }
                }
            }

            while (!secondQueue.isEmpty()) {
                key = secondQueue.poll();
                neighbors = tree.get(key);
                if (neighbors != null) {
                    path++;
                    for (String neighbor : neighbors) {
                        if (neighbor.equals(to)) {
                            return path;
                        } else {
                            firstQueue.add(neighbor);
                        }
                    }
                }

            }

        }
        return 0;
    }
于 2013-04-30T19:34:07.550 に答える