From charlesreid1

Depth first search notes

Depth first search utilizes backtracking and recursion to explore each node of a tree, or each vertex of a graph, exactly once.

On a graph, depth-first search is a crucial building block of several algorithms related to connectivity, such as finding cycles, determining of two vertices are connected, and constructing spanning trees.

For an example of depth-first search on a graph, see traveling salesperson problem page.




Traversals on trees:

Breadth-first search and traversal on trees:

  • BFS - breadth first search
  • BFT - breadth first traversal

Depth-first search and traversal on trees:

  • DFS - depth first search
  • DFT - depth first traversal

OOP design patterns: