Depth-First Search

A Graph Search algorithm:

  • explore aggressively, backtrack only if needed
  • uses FILO / recursion

Algorithm

DFS(graph $G$, start vertex $s$):

  • mark $s$ as explored
  • for every edge $(s, v)$
    • if $v$ is unexplored
    • DFS($G$, $v$)

running time [math]O(n + m)[/math]

DFS applications

See also


Sources

Machine Learning Bookcamp: Learn machine learning by doing projects. Get 40% off with code "grigorevpc".

Share your opinion