DFS递归困境

我正在尝试编写一个算法来确定是否连接了有向图中的两个节点。足够简单，但我挂在DFS的递归实现上。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;

有没有更好的方式来写这个？主要的麻烦是让算法继续搜索，如果有一个小姐，但一旦你有一个匹配停止搜索。我想有一个干净的方式来做到这一点...？

来源

2017-09-10 stackoverflow_sucks

你为什么觉得这很丑？看起来没问题。 – algrid

关于这条线的唯一难看的部分是缺少花括号。否则看起来很好。 – Carcigenicate

假设您的实施是正确的，这看起来如何？

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

来源

2017-09-10 16:25:07 displayName

DFS递归困境

回答

相关问题