Depth First Search

Figure denotes the animation of a DFS traversal . Note how it traverses to the depths and backtracks.

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

In depth-first search (DFS) we start from a particular vertex and explore as far as possible along each branch before retracing back (backtracking). In DFS also we have to keep track of the visited vertices. When implementing DFS, we use a stack data structure to support backtracking.

Pseudocode:

Input: A graph G and a vertex v of G

Output: All vertices reachable from v labeled as discovered

A recursive implementation of DFS:

procedure DFS(G, v) is
    label v as discovered
    for all directed edges from v to w that are in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
            recursively call DFS(G, w)

Time and Space Complexity:

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 ${\displaystyle O(|V|+|E|)}$, linear in the size of the graph. In these applications it also uses space ${\displaystyle O(|V|)}$ in the worst case to store the stack of vertices on the current search path as well as the set of already-visited vertices.

Applications

·        Used to find a path between two vertices.

·        Used to detect cycles in a graph.

·        Used in topological sorting.

·        Used to solve puzzles having only one solution (e.g., mazes)