Depth-first search

Depth-first-tree

Depth-First-Search

graph.traversal.example

Tree_edges

If-then-else-control-flow-graph

Graph.traversal.example

File:MAZE 30x20 DFS.ogv 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 in the case of a graph) and explores as far as possible along each branch before backtracking.

Algorithm

The basic idea of DFS is to start from the root (or any arbitrary node) and mark the node and move to an adjacent unmarked node and continue this process until there is no unmarked adjacent node. Then backtrack and check for other unmarked nodes and traverse them. Finally, print the nodes in the path.

Pseudocode

The pseudocode for DFS is as follows:

Recursive 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)

Iterative DFS:

procedure DFS-iterative(G, v) is
  let S be a stack
  S.push(v)
  while S is not empty do
    v = S.pop()
    if v is not labeled as discovered then
      label v as discovered
      for all edges from v to w in G.adjacentEdges(v) do
        S.push(w)

Applications

DFS is used in various applications, including:

• Topological sorting
• Finding connected components
• Pathfinding
• Solving puzzles with only one solution, such as mazes

Properties

• DFS can be implemented using recursion or using a stack.
• The time complexity of DFS is O(V + E), where V is the number of vertices and E is the number of edges.
• The space complexity of DFS is O(V) in the worst case.

Related Algorithms

• Breadth-first search
• Dijkstra's algorithm
• A* search algorithm

See Also

• Graph theory
• Tree traversal
• Algorithm

Related Pages

• Graph (discrete mathematics)
• Tree (data structure)
• Breadth-first search
• Topological sorting
• Pathfinding