DFS再帰問題

Question

有向グラフの2つのノードが接続されているかどうかを判断するアルゴリズムを作成しようとしています。十分にシンプルですが、DFSの再帰的実装でハングアップしています。

働く私のソリューションは、非常に醜いです：

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

は特に、このラインは醜いです：

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

はこれを書くための良い方法はありますか？主な問題は、ミスがあった場合は検索を続行するアルゴリズムを取得することですが、一致したら検索を停止します。私はこれを行うきれいな方法があると思います...？

Answer 1

実装が正しいとすれば、どのように見えますか？

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