I wrote a very simple implementation of cycle detection in an undirected graph; I'm not interested in applying it to any real-life case: it's just for explaining the basic idea behind cycle detection in a CS lesson.
I went for recursive DFS, and unlike other implementations I found on the internet, I used just one set for the visited nodes (instead of having a set for the visited nodes and another one for the ancestors):
boolean hasCycleDfs(Node current, Set<Node> visited) {
if (visited.contains(current)) {
return true;
}
visited.add(current);
for (Node neighbour: current.neighbors) {
if (hasCycleDfs(neighbour, visited)) {
return true;
}
}
visited.remove(current);
return false;
}
I wrote a couple of tests and they're green:
@Test
public void test() {
List<Node> nodes = IntStream
.range(1, 8)
.mapToObj(Node::new)
.collect(Collectors.toList());
Node n1 = nodes.get(0);
Node n2 = nodes.get(1);
Node n3 = nodes.get(2);
Node n4 = nodes.get(3);
Node n5 = nodes.get(4);
Node n6 = nodes.get(5);
Node n7 = nodes.get(6);
n1.add(n2).add(n3);
n2.add(n4);
n3.add(n4).add(n6);
n4.add(n6).add(n7);
n5.add(n1);
n6.add(n5);
assertTrue(hasCycleDfs(n1, new HashSet<>()));
cleanNodes(nodes);
n1.add(n2);
n2.add(n3);
n3.add(n4);
n4.add(n1);
assertTrue(hasCycleDfs(n1, new HashSet<>()));
cleanNodes(nodes);
n1.add(n2).add(n5).add(n3);
n2.add(n3).add(n5);
n3.add(n4).add(n5);
n4.add(n5);
assertFalse(hasCycleDfs(n1, new HashSet<>()));
cleanNodes(nodes);
n1.add(n2).add(n3);
n2.add(n3);
assertFalse(hasCycleDfs(n1, new HashSet<>()));
}
void cleanNodes(List<Node> nodes) {
nodes.forEach(Node::clearNeighbours);
}
This is the Node class:
class Node {
int val;
Set<Node> neighbors = new HashSet<>();
Node(int val) {
this.val = val;
}
public Node add(Node child) {
neighbors.add(child);
return this;
}
public void clearNeighbours() {
neighbors.clear();
}
@Override
public String toString() {
return "[" + val + "]";
}
@Override
public boolean equals(Object o) {
Node node = (Node) o;
return val == node.val;
}
@Override
public int hashCode() {
return val * 31;
}
}
Do you see any edge case I didn't take into account that will give a wrong answer?