java - 在 Java 中检测 Hashmap 中的循环依赖

Question

我有一个哈希图：

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

非循环情况的示例可能是：

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

我建议您阅读并实施 Tarjan 的算法。

Tarjan 算法

我前段时间用过。这是相当有效的。

也可以看看：

在有向图中检测循环的最佳算法

Answer 2

这是仅基于您的示例的粗略实现。我建议针对其他示例进行测试。

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