3

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

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

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

2 回答 2

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建议的那样，您确实有一个无法达到的目标。你应该检查你是否真的到达了结束节点。请注意，您的图形数据结构对有向图进行建模，因此如果要将输入解释为无向边，则必须为每行输入插入两条有向边。

另请注意，您不会将初始节点标记为可见，而当您将所有其他节点添加到队列中时，它们将被标记为可见。您也应该标记第一个。

编辑：
粘贴（几乎）完整的代码后，我通过以下方式对其进行了修复：

  • 添加了两个通配符导入，forjava.util.*和java.io.*. 通配符导入又快又脏。
  • 在最后添加关闭}以关闭类定义。
  • basic在输入数据中添加了带有单词的行。System.exit(1)如果缺少该关键字，您确实应该这样做，而不是继续使用不一致的状态。

通过这些修改，我测试了两个城市的所有可能组合，总是按两个顺序排列，并且包括形成一个城市的路径。任何地方都没有值的证据null，无论是在输出中还是作为打印异常的原因。

于 2012-08-02T18:48:08.293 回答
-1

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

例如，假设输入是：

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

您想从 A 到 E。这可以通过 A、B、E 来完成。但是当您构建地图时，您将为 B、A 创建一个边缘条目。然后您将编写 B、C，覆盖B, A. 然后你写 E, B. 很好。然后你写E，D，覆盖E，B。所以当你完成后，边缘图中的所有内容都是（B，C）和（E，D）。然后，您尝试从 E 向后走。您会找到 E，D。但这是错误的：您想要 E，B，但它被覆盖了。当你试图找到 D 的入口时，没有，所以不可能回到 A。

第二个问题是您说目标是找到从头到尾的最短路径。但是您没有做任何事情来找到最短路径：一旦找到任何路径，您就会停止寻找。原则上，您确实需要找到所有可能的路径，然后从该列表中选择最短的路径。（或者希望，以一种或另一种方式消除更长的路径。）

于 2012-08-02T18:55:27.977 回答