從地圖中添加到堆棧

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

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暗示。你應該檢查你是否真的到達了最終節點。請注意，您的圖datra結構模型指導的圖，所以如果您想要將輸入解釋爲不受限制的邊，則必須爲每行輸入插入兩個有向邊。

另請注意，您不會將初始節點標記爲可見，而將所有其他節點標記爲您將它們添加到隊列時所看到的標記。你也應該標記第一個。

編輯：
後您粘貼您的（幾乎）完整的代碼，我固定它在以下幾個方面：

• 增加了兩個通配符進口，爲java.util.*和java.io.*。通配符導入很快且很髒。
• 在最後添加了關閉}以關閉類定義。
• 爲您的輸入數據添加了一行文字basic。如果該關鍵字缺失，您確實應該System.exit(1)，而不是繼續進行不一致的狀態。

通過這些修改，我測試了兩個城市的所有可能的組合，總是以兩種順序，並且包括路徑形成一個城市到自己。沒有證據顯示任何地方的值，既不是輸出值也不是打印異常的原因。

Answer 2

我在這裏看到一些可能的問題。直接原因可能是這樣的：你的邏輯隱含地假設只有一種方法可以到達任何給定節點。雖然這可能是真的，但我懷疑它。如果有兩種方法可以訪問同一個節點，則可以在地圖中覆蓋第一個和第二個節點。

例如，假設輸入爲：

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.

第二個問題是您說目標是從頭到尾找到最短路徑。但是你沒有找到最短路徑：一旦找到任何路徑，你就停止尋找。原則上，您確實需要找到所有可能的路徑，然後從該列表中選擇最短路徑。 （或者希望能夠隨時消除更長的路徑，以這種或那種方式進行。）