Profondeur de recherche d'abord avec retours en arrière en Java

Question

Je suis en train d'écrire un DFS pour rechercher le graphe pondéré suivant:

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, 

ce code a Je DFS du tutoriel sur corsera graphiques java. ce que je pensais qu'il ferait est de trouver un chemin à travers un graphique d'un nœud à l'autre - mais il reste bloqué et continue d'ajouter des nœuds à la pile encore et encore jusqu'à ce qu'il casse.

Comment est-ce que je modifierais ce code pour vérifier plutôt un chemin de la source à la cible où les poids de bord du produit aller sont supérieurs à 1.0? Je suis un peu coincé ...

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

toute aide serait appréciée.

Answer 1

Je ne peux pas tester car je n'ai pas la classe GraphAdjMatrix, mais je crois que le problème est que les nœuds sont ajoutés à visit, mais il n'y a pas de vérification pour voir si un nœud a déjà été visité. Essayez comme suit:

public à trouver la carte (finale GraphAdjMatrix adjMatrix, source int, objectif 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; 

}