Cycle detection in undirected graphs with recursive DFS

Question

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?

Answer 1

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);
a.add(b);
b.add(a);

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) {
 visited.add(current);
 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);

• Andrea Iacono: Thanks Marc, super useful review!
• Marc: @AndreaIacono glad I could help. Any reason for the downvote?
• Andrea Iacono: 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?
• Andrea Iacono: I also realized that my tests are incosistent with the title of the question: they build a directed graph instead of an undirected graph
• Marc: @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.