Java 9 Data Structures and Algorithms

Cycle detection

One of the uses of a traversal is cycle detection. A connected undirected graph without any cycle is a tree. A directed graph without any cycle is called a directed acyclic graph (DAG). Cycle detection in graphs can be done in a very similar manner. In the case of an undirected graph, if we do a DFS and the same node is visited twice as the target of an edge, there is a cycle. Since the edge is undirected, we are satisfied if either the source or the target has not been seen before.

In the case of a directed graph, visiting the same node twice is not enough if you want to know whether there is a cycle; we should also consider the direction of the edges. This means while traversing the edges, we need to know whether we can reach ...