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遞歸困境

回答

相關問題