Identifying the depth-first search pattern

There are many graph problems that can only be solved efficiently by depth-first search. These are generally medium or hard problems where we need to process all nodes in a path from a source node to a destination node. In most cases, we need to find the aggregated value of a function f over all the nodes in some or all paths from a source node to a destination node. Some problems may even go further and require further aggregating the path aggregates over another function g. For most problems, this results in a single value that represents the combined contribution of all paths from the source node to the destination node.

If the problem statement or its solution follows the generic template below, it can be solved using depth-first search.