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.

## 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

## References

“Depth-First Search.” 2022.

*Wikipedia*, June. https://en.wikipedia.org/w/index.php?title=Depth-first_search&oldid=1091833357.