java - 从 map 添加到堆栈

Question

我正在为学校做一个项目，要求我们找到两点之间的最短路径。基本上我使用广度优先搜索来遍历图表，然后使用 map 来跟踪每个城市的前身。我的想法是，当我到达终点时，我将使用边缘 map 找出一个城市是如何到达的，并且基本上是倒退的。但是，当我尝试从 map 中提取值时，我得到的都是空值，即使当我打印出内容时它显示那里有东西。如果有人可以帮助我找出问题所在，我将不胜感激。

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

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());
        }
    }
}

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 值的证据，无论是在输出中还是作为打印异常的原因。