深度優先搜索在Java

回溯我想寫一個DFS搜索以下加權圖：深度優先搜索在Java

0  1.  2.  3  4.  5.  6.  7.  8. 
0: 0.0, 0.68, 78.926, 6.205, 6.707, 48.45, 0.59, 0.704, 0.978, 
1: 1.47, 0.0, 116.021, 9.129, 9.869, 71.284, 0.869, 1.09, 1.44, 
2: 0.012, 0.0086, 0.0,  0.079, 0.085, 0.615, 0.007, 0.009, 0.012, 
3: 0.161, 0.109, 12.65, 0.0, 1.081, 7.807, 0.095, 0.119, 0.171, 
4: 0.149, 0.101, 11.764, 0.925, 0.0, 7.225, 0.088, 0.111, 0.146, 
5: 0.020, 0.014, 1.63, 0.128, 0.134, 0.0, 0.012, 0.015, 0.02, 
6: 1.69, 1.15, 142.86, 10.53, 11.36, 83.33 0.0, 1.254, 1.656, 
7: 1.42, 0.917, 111.11, 8.403, 9.01, 66.667, 0.797, 0.0, 1.321, 
8: 1.022, 0.69, 83.33, 5.848, 6.849, 50.0, 0.604, 0.757, 0.0,

我從Java的圖形中的corsera教程此DFS代碼。我認爲它會做的是通過圖形從一個節點到另一個節點找到一條路徑 - 但它只是被卡住，並且一直不停地向堆棧添加節點，直到它斷裂。

我該如何改變這段代碼，而不是檢查從源到目標的產品邊緣權重大於1.0的路徑？我有點卡住了...

DFS

public Map<Integer, Integer> find(final GraphAdjMatrix adjMatrix, int source, int goal) { 

    stack = new Stack<>(); 
    this.visited = new HashSet<>(); 
    this.parentMap = new HashMap<>(); 

    stack.push(source); 
    visited.add(source); 

    while (!stack.isEmpty()) { 
     int curr = stack.pop(); 

     if (curr == goal) 
      return parentMap; 

     for (int n : adjMatrix.getNeighbors(curr)) { 
      visited.add(n); 
      parentMap.put(n, curr); 
      stack.push(n); 
     } 
    } 
    return parentMap; 
}

任何幫助，將不勝感激。

來源

2016-12-14 StillLearningToCode

嗨，有趣的，但......如果你把一個例子這將是很好與樹回溯的圖片（顯然不是所有的節點，只有一個部分有一個想法） – Dani

我不能測試，因爲我沒有GraphAdjMatrix類，但我相信問題是節點被添加到visit，但沒有檢查是否已經訪問了一個節點。嘗試如下：

公共地圖的發現（最終GraphAdjMatrix adjMatrix，INT源，詮釋目標）{

stack = new Stack<>(); 
this.visited = new HashSet<>(); 
this.parentMap = new HashMap<>(); 

stack.push(source); 
visited.add(source); 

while (!stack.isEmpty()) { 
    int curr = stack.pop(); 

    if (curr == goal) 
     return parentMap; 

    for (int n : adjMatrix.getNeighbors(curr)) { 
     if (! visited.contains(n)) { 
     visited.add(n); 
     parentMap.put(n, curr); 
     stack.push(n); 
     } 
    } 
} 
return parentMap;

}

來源

2016-12-14 06:47:34

深度優先搜索在Java

回答

相關問題