从映射中添加到堆栈

Question

我正在为学校的一个项目工作，需要找到两点之间的最短路径。基本上我使用广度优先搜索来遍历图形，然后使用映射来跟踪每个城市的前任。我的想法是，当我到达终点时，我将使用边缘映射来查找如何到达城市，并从本质上逆向工作。但是，当我尝试从映射中提取值时，我得到的只是null，即使当我打印出内容时，它显示有东西。如果有人可以帮助我找到问题，我会很感激。

带有每个城市及其邻居的输入文件的内容:

basic
Bismark      Fargo
Minneapolis  Chicago
StPaul       Chicago
Minneapolis  StPaul
Minneapolis  Fargo
Fargo        GrandForks

代码 （更正版本，因此此代码不再表现出所描述的问题）：

import java.util.*;
import java.io.*;

public class BFSBasics {
    public static void main(String[] args) throws FileNotFoundException {
        Map<String, List<String>> graph = new HashMap<>();
        openFile(graph, args[0]);
        String start = args[1];
        String end = args[2];

        BFS(graph, start, end);
    }

    public static void openFile(Map<String,List<String>> graph, 
            String file) 
            throws FileNotFoundException{
        Map<String,List<String>> aGraph = new HashMap<>();
        try (Scanner scan = new Scanner(new File(file))){
            if(!scan.next().equals("basic")){
                System.err.println("File cannot be read.");
                System.exit(1);
            }else{
                while(scan.hasNext()){
                    String city1 = scan.next();
                    String city2 = scan.next();
                    addEdge(graph, city1, city2);
                    addEdge(graph, city2, city1);                   
                }   
            }   
        }
    }

    private static void addEdge(Map<String, List<String>> graph, String city1,
            String city2){
        List<String> adjacent = graph.get(city1);
        if(adjacent == null){
            adjacent = new ArrayList<>();
            graph.put(city1, adjacent);
        }
        adjacent.add(city2);
    }

    public static void BFS(Map<String, List<String>> graph, String start,
            String end) {
        boolean done = false;
                //cities that still need to be worked on
        Queue<String> work = new ArrayDeque<>();
                //cities that have already been seen
        Set<String> seen = new HashSet<>();
                //cities predecessor i.e. how it was gotten to
        Map<String, String> edges = new HashMap<>();
        LinkedList<String> path = new LinkedList<>();

        String city = start;
        work.add(start);
        while (!done && !work.isEmpty()) {
            city = work.remove();
            for (String s : graph.get(city)) {
                if (!seen.contains(s)) {
                    edges.put(s, city);
                    work.add(s);
                    seen.add(s);
                    if (s.equals(end)) {
                        done = true;
                    }
                }
            }
        }

        //Work backwards through the edges map and push onto the path stack
        path.push(end);
        String temp = edges.get(end);
        while(!temp.equals(start)){
            path.push(temp);
            temp = edges.get(path.peek()};
        }
        path.push(start);
        //print out the path
        while(!path.isEmpty()){
            System.out.println(path.pop());
        }
    }
}

- Eric

---

能否让我们看一下您的数据集？起始节点无法到达终止节点可能是导致错误的原因。 - hcarver

这就是你要找的吗？ - Eric

如果从起点无法到达终点，那么就不会有从终点到任何可从起点到达的节点的边，因此edge.get(end)将为null。 - Soronthar

好的，既然它对我仍然有效，那么我可以问一下，你的命令行参数是什么？ - jeff

很抱歉回复晚了。我已经找到了问题，并在上面的代码中调整了我的答案。正如MvG所指出的那样，我没有正确地访问地图并将城市推进堆栈中。在我的原始代码中，我走得太远了，因此出现了NullPointerException。感谢大家的帮助。 - Eric

Answer 1

您的路径构建代码存在问题：

path.push(end);                 // push node (n - 1)
String temp = edges.get(end);   // temp = node (n - 2)
while(!temp.equals(start)){
    path.push(edges.get(temp)); // push node (n - 3) down to and including node 0
    temp = path.peek();         // temp = node (n - 3) down to and including node 0
}
path.push(start);               // push node 0

所以节点（n - 2）永远不会被推入路径，而节点0将被推两次。

但除此之外，程序对我来说是有效的。因此，正如Hbcdev所建议的那样，你可能真的有一个无法到达的目标。你应该检查一下是否实际上到达了终点节点。请注意，你的图数据结构模拟了一个有向图，因此如果你想将输入解释为无向边，则需要为每个输入行插入两个有向边。

另请注意，当你将节点添加到队列时，你没有将初始节点标记为已访问，而所有其他节点都将被标记为已访问。你也应该标记第一个节点。

编辑：
在你粘贴了（几乎）完整的代码后，我进行了以下修复：

• 添加了两个通配符导入，分别是java.util.*和java.io.*。通配符导入是快速而不太规范的。
• 在类定义的最后添加了一个闭合的}。
• 添加了一行带有单词basic的输入数据。如果缺少该关键字，您应该System.exit(1)，而不是继续使用不一致的状态。

通过这些修改，我测试了所有可能的两个城市的组合，总是包括从一个城市到自身的路径。无论是输出还是打印异常的原因，都没有发现null值的任何证据。

- MvG

---

我现在明白了我的问题。我对栈的处理方式不正确。还有，谢谢你关于 system.exit(1) 的提示。 - Eric

@Eric，在你确认后不要忘记分享你的见解。要么接受一个合适的答案，要么写下你自己的答案。我们都希望了解你遇到的问题，这样像我和Jeff这样的人就不会犯同样的错误了。 - MvG

Answer 2

我看到这里可能有几个问题。直接的原因可能是：你的逻辑隐含地假设到达任何给定节点只有一种方法。虽然这可能是真的，但我怀疑。如果有两种方法到达同一个节点，你会在映射中用第二种方法覆盖第一种方法。

例如，假设输入是：

A->B
C->B
B->E
D->E

你想要从A到E。可以通过经过A、B、E来实现。但是当你建立地图时，你会为B创建一个边缘条目A,B。然后您会编写B,C，覆盖B,A。然后您编写E,B。好的。然后您编写E,D，覆盖E,B。因此，完成后，在边缘映射中的所有内容都是(B,C)和(E,D)。接着你试着从E反向走。你找到了E,D。但这是错误的：你想要E,B，但被覆盖了。当你尝试查找D的条目时，没有找到，因此无法返回A。

第二个问题是，你说目标是从起点到终点找到最短路径。但你什么也没做来找到最短路径：一旦找到任何路径，就停止寻找。你确实需要原则上找到所有可能的路径，然后从该列表中选择最短的路径。（或希望一路上消除更长的路径。）

- Jay

---

我相信你误解了。由于每个节点在被访问后都会被标记为“已访问”，因此每个节点只会有一个前任。不会覆盖。并且，由于BFS按非递减跳数顺序访问路径，所以较短的路径将首先被遇到。因此，第一个找到的路径将是跳数最少的最短路径。地理距离是另一个问题，但显然不是这个问题的一部分。 - MvG