深さ優先探索は、Java

Question

にバックトラックで私は、次の重み付きグラフを検索するDFSを記述しようとしています：

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より大きいソースからターゲットへのパスを代わりにチェックするにはどうすればよいですか？私は任意の助けをいただければ幸い

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

...

DFS

ソートのこだわっています。

Answer 1

私はGraphAdjMatrixクラスがないのでテストできませんが、問題はノードがvisitに追加されていると考えられますが、ノードが既に訪問されたかどうかを確認するチェックはありません。次のように試してみてください。

公共マップ検索（最終GraphAdjMatrix adjMatrix、int型のソース、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; 

}