我尝试使用以下代码为有向图实现“getCycles”函数：
private boolean getCycles(Vertex v, HashMap<Vertex, DiscoverStatus> d, HashMap<Vertex, Vertex> r) {
d.put(v, DiscoverStatus.DISCOVERING);
HashSet<Vertex> neighbors = getNeighbors(v);
for (Vertex n : neighbors) {
if (d.get(n) == DiscoverStatus.DISCOVERING) {
r.put(v, n);
return true;
}
if (d.get(n) == DiscoverStatus.UNDISCOVERED && getCycles(n, d, r) == true)
r.put(v, n);
return true;
}
d.put(v, DiscoverStatus.DISCOVERED);
return false;
}
其中 Vertex 类仅具有一个 String 字段，并且DiscoverStatus/getNeighbors定义为：
public enum DiscoverStatus {
UNDISCOVERED, DISCOVERING, DISCOVERED
}
HashMap<Vertex, HashSet<Vertex>> adjacencyMap = new HashMap<>();
public HashSet<Vertex> getNeighbors(Vertex vertex) {
return this.adjacencyMap.get(vertex);
}
我的问题是：这种用于循环检测的“着色”算法（如果不熟悉，请参见此处）以某种方式提供检测“父”节点的方法吗？例如，使用以下有向图：
A
J
B
D
G
E
H
F
B
D
G
C*
A
我在 C 上打了星号，因为它指向 A，在它们之间创建了一个循环。然而，A 是这里的父级。我怎样才能在getCycles算法或其他方面检测到这一点？起初我想我只是先进行深度优先搜索，看看一个是否包含另一个，然后我才意识到它们都相互包含。也许我应该这样做，但使用计数器变量来跟踪“深度”？我只是不知道如何开始。