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 the same node we started with. This requires us to remember the entire path while doing a DFS. This is why we use a recursive helper method to detect a cycle in a directed graph. We create the helper method for the directed cycle first. The checkDirectedCycleFromVertex...