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