DfsAlgorithm

A depth first search starts from a specified node and traverses the neighbors within a branch as deeply as possible (i.e., without visiting any vertex twice) before backtracking.

A depth first search traversal induces a DFS forest that may consist of more than one DFS tree. Based on these trees, the edges are divided into four categories (see example):

• Tree Edges: The edges of the DFS forest.
• Back edges: Non-tree edges that connect nodes with their ancestors in the DFS tree. Self-loops are also considered as back edges.
• Forward edges: Edges that connect nodes of the DFS tree to one of their descendants.
• Cross edges: All other edges.

During a DFS run each node of the graph can be in one of the following states:

• Undiscovered: A node that has not been visited yet.
• Discovered but not finished: A node that has been already visited, but has not been completed yet, i.e. it is still part of an active path of the DFS tree.
• Finished: A node that has been completed, i.e. it has been visited before and is not part of an active path of the DFS tree anymore.

Graph algorithms, which are based on a depth first search, can extend this class and override appropriate callback methods provided by this class.

Example of a DFS traversal. Node labels indicate the order in which nodes are visited. Solid edges are the edges of the DFS tree while dashed edges represent back, forward and cross edges.