java - 字符串路径 BFS

Question

我试图找到两个字符串之间的最短路径，并返回一个整数，表示已采取了多少步。鉴于我有一个 HashMap ，其中每个 String(key) 都有一个String[](object) 包含所有字符串邻居。

这段代码是我写的。我只是拿了一个基本的 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}

从鱼到牛我需要两个步骤。从鱼到山羊，从山羊到鱼。

因此，如果您有任何想法，请随时分享:)

Answer 1

我正在考虑使用 2 个队列。我会将from单词排入 firstQueue，虽然firstQueue它不为空，但如果该邻居仍然不等于 ，我将执行交替逻辑以将邻居存储在另一个队列中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;
    }