DFS

1. Definition

Depth-first Search(DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithms starts at the root node (selecting some arbitarary node as the root nodes in the case of the graph) and explores as far as possible along each branch before backtracking.

 

2. Properties

The time and space analysis of DFS differs according to its application area. In theoretical computer science, DFS is typically used to traverse an entire graph, and takes time O(V+E), where V is the number of vertices and E the number of edges.

DFS starting at the node A, assuiming that the left edges in the shown graph are chosen before right edges, and assuming the search remembers previously visited nodes and will not repeat them, will visit the nodes in the following order : A, B, D, F, E, C, G.

 

https://en.wikipedia.org/wiki/Depth-first_search