# Cycle detection in undirected graphs with recursive DFS

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

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

assertTrue(hasCycleDfs(n1, new HashSet<>()));

cleanNodes(nodes);
assertTrue(hasCycleDfs(n1, new HashSet<>()));

cleanNodes(nodes);
assertFalse(hasCycleDfs(n1, new HashSet<>()));

cleanNodes(nodes);
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;
}

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?

The code looks clean and organized, but there is an issue with the implementation.

## Undirected graph

Consider an undirected graph A - B:

• B is neighbor of A
• A is neighbor of B

Using the current implementation I would create the graph like this:

Node a = new Node(1);
Node b = new Node(2);

Such graph is not cyclic, but the method hasCycleDfs returns true.

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)

The reason for the set of ancestors is to handle this case.

## Testing

• Is good practice to have one method for test case, instead of a single method with all the tests. It will help you pinpoint the failing test quicker without having to look at the code.
• Once you have multiple @Test methods, you can clean the state in a method annotated with @Before (@BeforeEach in Junit5) or simply recreate the graph from scratch every time.

## Minor improvements

• The methods of Node are public unlike the class and instance variables. Use the access modifiers consistently.
• In a non‐academic context, the method hasCycleDfs should be private as it needs to be called with and empty set:
boolean hasCycleDfs(Node current) {
return hasCycleDfs(Node current, new HashSet<>());
}
private boolean hasCycleDfs(Node current, Set<Node> visited) {
//...
}

## Rewrite

Actually, there is no need for a set of ancestors, a pointer to the parent is enough:

boolean hasCycleDfs(Node current, Set<Node> visited, Node parent) {
for (Node neighbour : current.neighbors) {
if (!visited.contains(neighbour)) {
if (hasCycleDfs(neighbour, visited, current)) {
return true;
}
} else if (!neighbour.equals(parent)) {
// If the node is visited and not parent of
// the current node, then there is a cycle
return true;
}
}
return false;
}

And you can use it like:

hasCycleDfs(n1, new HashSet<>(), null);
• Thanks Marc, super useful review! Nov 11, 2020 at 8:39
• @AndreaIacono glad I could help. Any reason for the downvote?
– Marc
Nov 11, 2020 at 8:56
• actually I pressed it by mistake while accepting your anwser, and now it doesn't allow me to edit anymore (unless you edit the answer). Can you edit it? Nov 11, 2020 at 9:21
• I also realized that my tests are incosistent with the title of the question: they build a directed graph instead of an undirected graph Nov 11, 2020 at 9:23
• @AndreaIacono edited the answer. Yeah, the tests seems to build a directed graph. An additional suggestion is to create a class Graph with a method addEdge(a,b) to simplify the graph creation.
– Marc
Nov 11, 2020 at 9:36