Tiefensuche mit in Java Rückzieher

Question

Ich versuche, eine DFS zu schreiben, um die folgenden gewichteten Graphen suchen:

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, 

bekam ich diesen DFS-Code aus dem corsera Tutorial auf Java-Graphen. Was ich dachte, wäre, einen Pfad durch ein Diagramm von einem Knoten zum anderen zu finden - aber es bleibt einfach stecken und fügt dem Stapel immer wieder Knoten hinzu, bis es bricht.

Wie würde ich diesen Code ändern, um stattdessen nach einem Pfad von der Quelle zum Ziel zu suchen, wo das Kantengewicht des Produkts größer als 1,0 ist? Ich bin irgendwie stecken ...

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

jede mögliche Hilfe würde geschätzt.

Answer 1

Ich kann nicht testen, wie ich nicht die GraphAdjMatrix Klasse habe, aber ich glaube, das Problem ist, dass die Knoten visit hinzugefügt werden, aber es gibt keine Überprüfung, um zu sehen, ob ein Knoten bereits besucht wurde. Versuchen Sie wie folgt vor:

public Map Fund (endgültige GraphAdjMatrix adjMatrix, int Quelle, int Ziel) {

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; 

}