Detect Cycle in directed graph
如题,做法是用3个set,白表示还没visited的,灰表示正在visit的,黑表示已经visit完了的。如果在visit的途中发现有正在被visit的(在graySet里)就表示这个点能通过其他的点到达,所以有环。S:O(V)T: O(E +V)
public boolean isCyclic(List<DirectedGraphNode> graph) {
if (graph == null || graph.size() == 0) {
return false;
}
HashSet<DirectedGraphNode> whiteS = new HashSet<>();
HashSet<DirectedGraphNode> grayS = new HashSet<>();
HashSet<DirectedGraphNode> blackS = new HashSet<>();
for (DirectedGraphNode node : graph) {
whiteS.add(node);
}
while (whiteS.size() > 0) {
DirectedGraphNode start = whiteS.iterator().next();
if (dfs(whiteS, grayS, blackS, start)) {
return true;
}
}
return false;
}
private boolean dfs(HashSet<DirectedGraphNode> whiteS, HashSet<DirectedGraphNode> grayS,
HashSet<DirectedGraphNode> blackS, DirectedGraphNode start) {
move(start, whiteS, grayS);
for (DirectedGraphNode nei : start.neighbors) {
if (blackS.contains(nei)) {
continue;
}
if (grayS.contains(nei)) {
return true;
}
if (dfs(whiteS, grayS, blackS, nei)) {
return true;
}
}
move(start, grayS, blackS);
return false;
}
private void move(DirectedGraphNode start, HashSet<DirectedGraphNode> from, HashSet<DirectedGraphNode> to) {
from.remove(start);
to.add(start);
}
class DirectedGraphNode {
int label;
List<DirectedGraphNode> neighbors;
DirectedGraphNode(int x) {
label = x;
neighbors = new ArrayList<DirectedGraphNode>();
}
}
Last updated