Detecting a cycle in a directed graph via an adjacency list implementation and a recursive DFS

Question

Here's my attempt. I iterate through each vertex in the graph and do a DFS to see if I reach back on a vertex I already visited in this vertex's iteration. It seems to work but I am not satisfied with how I short-circuit my code when it found a cycle using if clauses, could not think of a better way to do that.

public boolean isCyclic(Map<T, List<T>> adjacencyList) {
 for (T node: adjacencyList.keySet()) {
 Set<T> visited = new HashSet<>();
 visited.add(node);
 if (isCyclic(visited, node) == true)
 return true;
 }
 return false;
}
private boolean isCyclic(Set<T> visited, T node) {
 boolean retval;
 for (T connectedNode: map.get(node)) {
 if (visited.contains(connectedNode)) {
 // We've reached back to a vertex, i.e. a back-edge
 return true;
 } else {
 visited.add(connectedNode);
 if (isCyclic(visited, connectedNode) == true)
 return true;
 }
 }
 return false;
}

Answer 1

I didn't find another way to do it, but I will give you some tips on the current implementation.

Always add curly braces to loop & if

In my opinion, it's a bad practice to have a block of code not surrounded by curly braces; I saw so many bugs in my career related to that, if you forget to add the braces when adding code, you break the logic / semantic of the code.

Simplify the boolean conditions.

In both of the method, you can simplify the boolean validations.

Equivalence

isCyclic(visited, node) == true can be isCyclic(visited, node)

Before

if (isCyclic(visited, node) == true) {
 return true;
}

After

if (isCyclic(visited, node)) {
 return true;
}

Code reduction

In the second method, instead of using the java.util.Set#contains method, you can check the returned boolean of the java.util.Set#add directly; this will allow you to remove an instruction.

Documentation:

Returns:
true if this set did not already contain the specified element

Basic example

Set<Character> set = new java.util.HashSet<>(Set.of('A', 'B', 'C'));
System.out.println(set.add('A')); // false
System.out.println(set.add('D')); // true

This will add the element, if not already present and return true if it was not present.

Before

if (visited.contains(connectedNode)) {
 // We've reached back to a vertex, i.e. a back-edge
 return true;
} else {
 visited.add(connectedNode);
 if (isCyclic(visited, connectedNode)) {
 return true;
 }
}

After

if (!visited.add(connectedNode)) {
 // We've reached back to a vertex, i.e. a back-edge
 return true;
} else {
 if (isCyclic(visited, connectedNode)) {
 return true;
 }
}

---

In the second method, you can remove the retval variable, since it does nothing.

• Lars Wissler: Upvoted just for the brackets with for/if part. i introduced so many errors when adding a second statement and forgetting to add the brackets and I swore never to write an if without brackets again.
• user2495123: Thank you for the handy advice, yes I got lazy about the curlies around the if condition :)