In depth first search, visit nodes in the graphs along the edges by traversing all the way to the end of the graph before backtracking. Use an outer loop to ensure every node is seen at least once. The result is a depth first search forest (a collection of trees), represented as a table with a row for each node and columns for parent, discovery time and finish time. The time is simply a counter that increments with each operation. We also need to keep track of whether the node was seen or not during the algorithm. When an edge is represented in the tree, it is a **tree edge**. This forest will not have all of the edges represented, specifically: * **back edge**: relationships from descendant to ancestor (graphs for which depth first search produces a back edge also have a cycle) * **cross edge**: edges between siblings (from the perspective of the root node) * **forward edge**: those from the source node to a node that was already discovered along a different path ("grandchildren" of the source node) We can detect additional edges from the output table of depth first search. - If a node's discovery time and finish time is wholly within another node's discovery time and finish time ($A_d < B_d < B_f < A_f$), there is a back edge from $A$ to $B$. - If the opposite is true ($B_d < A_d < A_f < B_f$), there is a forward edge from $A$ to $B$. - For two nodes where there is no overlap ($A_d < A_f < B_d < B_f$), there may be a cross edge. A graph has a cycle if and only if depth first search produces a back edge.