DFS Recursion Woes

Question

J'essaie d'écrire un algorithme pour déterminer si deux nœuds dans un graphe orienté sont connectés. Assez simple, mais je suis accroché sur ma mise en œuvre récursive de DFS.

Ma solution, qui fonctionne, est assez laid:

public static boolean isConnected (Node src, Node dst) { 
    HashSet<Node> visited = new HashSet<>(); 
    return isConnectedHelper(src, dst, visited); 
} 

private static boolean isConnectedHelper(Node src, Node dst, HashSet<Node> visited) { 
    if (src.equals(dst)) { 
     return true; 
    } 

    if (!visited.contains(src)) { 
     visited.add(src); 
     for (Node neighbor : src.neighbors) { 
      if (isConnectedHelper(neighbor, dst, visited)) 
       return true; 
     } 
    } 
    return false; 
} 

Notamment, cette ligne est laid:

 if (isConnectedHelper(neighbor, dst, visited)) 
      return true; 

Y at-il une meilleure façon d'écrire cela? Le principal problème est de faire en sorte que l'algorithme continue de chercher s'il y a un échec, mais d'arrêter de chercher une fois que vous avez une correspondance. J'imagine qu'il y a une façon propre de faire ça ...?

Answer 1

En supposant que votre implémentation est correcte, à quoi cela ressemble-t-il?

public static boolean isConnected (Node src, Node dst) { 
    HashSet<Node> visited = new HashSet<>(); 
    return isConnected(src, dst, visited); //Same name used, why not? Method overloading. 
} 

private static boolean isConnected (Node src, Node dst, HashSet<Node> visited) { 
    if (src.equals(dst)) return true; 
    if (visited.contains(src)) return false; 
    visited.add(src); 
    for (Node neighbor : src.neighbors) { 
     if (isConnected(neighbor, dst, visited)) return true; 
    } 
}