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.

(“Depth-First Search” 2022)

Algorithm

Iterative

procedure DepthFirstSearch (graph, rootNode) is
  define a Stack: stack
  define a Set: visited

  stack.push(rootNode)

  while not stack.empty() do
    node = stack.pop()
    if node not in visited then
      if node is a goal then
        return node
      for connectedNode in graph.connectedNodes(node) do
        stack.push(connectedNode)

Based on iterative algorithm in (“Depth-First Search” 2022). #+end_quote

Recursive

procedure DepthFirstSearch (graph, node) is
  define a Set: visited

  procedure DepthFirstSearchInner (graph, node) is
    if node in visited then
      return nil
    visited.add(node)

    if node is a goal then
      return node

    found = nil
    for connectedNode in graph.connectedNodes(node) do
      found = DepthFirstSearchInner(graph, connectedNode)
      if found then
         return found

    return nil

  return DepthFirstSearchInner(graph, node)

Based on recursive algorithm in (“Depth-First Search” 2022).

Complexity

Worst-case
Time\(\bigo{\href{/posts/cardinality}{\vert V \vert} + \href{/posts/cardinality}{\vert E \vert}}\)
Space\(\bigo{\href{/posts/cardinality}{\vert V \vert}}\)

Where \(V\) is the set of Vertices and \(E\) is the set of Edges.

Alternatives

Bibliography

“Depth-First Search.” 2022. Wikipedia, June. https://en.wikipedia.org/w/index.php?title=Depth-first_search&oldid=1091833357.