Graph Theory37 sections · 1633 units
Open in Course

Carrying State in DFS

The Backpack

Sometimes you do not traverse. You calculate something along the path. Examples: maximum value seen so far, number of nodes with a property, depth from root. To do this, add parameters to your DFS function. Pass state down the recursion tree. Update it before recursing to children.

Return values upward if needed. For instance, to track depth, pass depth\text{depth} as a parameter and call dfs(v,depth+1)\text{dfs}(v, \text{depth} + 1) for each child. This lets you compute path-dependent values during traversal.