檢測循環扶養在哈希映射在Java中

Question

我有非循環情況

Tables => Set of Parent Tables [ HashMap<String, HashSet<String>> ] 

例的一個HashMap可能是：

A -> [B,C] 
D -> [B,C] 
B -> [C] 
c -> [] 

循環情況的例子是：

A -> [B,C] 
B -> [C] 
C -> [A] 

我想拒絕循環情況，因此需要一個函數來檢測提供的散列表是否有任何循環：

public boolean hasDependencies ( HashMap<String, HashSet<String>> objectAndItsDependentsMap) 
{ 
    //Implementation 
} 

我已閱讀文章，建議算法來檢測週期，但是作爲java的新手無法使用該知識來化妝上述功能。請幫忙！

Answer 1

這裏是只能在自己的例如基於粗略的實現。我建議測試其他例子。

public boolean hasDependencies(Map<String, Set<String>> objectAndItsDependentsMap) { 
    for (String node : objectAndItsDependentsMap.keySet()) { 
     final Set<String> directNeighbors = objectAndItsDependentsMap.get(node); 
     for (String directNeighbor : directNeighbors) { 
      Set<String> next = objectAndItsDependentsMap.get(directNeighbor); 
      while (next != null) { 
       for (String n : next) { 
        next = objectAndItsDependentsMap.get(n); 
        if (next != null && (next.contains(n) || next.contains(node))) { 
         return true; 
        } 
       } 
      } 
     } 
    } 
    return false; 
} 

Answer 2

我建議您閱讀並實施Tarjan的算法。

Tarjan's algorithm

我用它前一段時間。這非常有效。

參見：

Best algorithm for detecting cycles in a directed graph