Depth First Search (DFS) | Graaf lib (original) (raw)

Depth First Search (DFS) is a fundamental graph traversal algorithm used to explore and analyze graphs, whether they are directed or undirected. DFS traverses deeper into the graph before backtracking to explore other branches.

The main difference to the BFS is the use of a stack instead of a queue.

The DFS algorithm is implemented with a stack and runs in O(|V| + |E|) time complexity for connected graphs, where |E| is the number of edges and |V| the number of vertices in the graph.

In summary, Depth First Search is a powerful and versatile algorithm for exploring graphs, but its limitations in handling weighted graphs and negative edge weights should be considered. It provides a straightforward way to explore a graph layer by layer and is particularly useful for unweighted graph scenarios and connectivity analysis.

The dfs_termination_strategy returns true when a certain condition is met, causing to terminate. The dfs_edge_callback is a function that is used as a callback during the DFS traversal to perform some action whenever an edge is traversed.

template <
    typename V, typename E, graph_type T,
    typename EDGE_CALLBACK_T = detail::noop_callback,
    typename SEARCH_TERMINATION_STRATEGY_T = detail::exhaustive_search_strategy>
  requires std::invocable<EDGE_CALLBACK_T &, edge_id_t &> &&
           std::is_invocable_r_v<bool, SEARCH_TERMINATION_STRATEGY_T &,
                                 vertex_id_t>
void depth_first_traverse(
    const graph<V, E, T> &graph, vertex_id_t start_vertex,
    const EDGE_CALLBACK_T &edge_callback,
    const SEARCH_TERMINATION_STRATEGY_T &search_termination_strategy =
        SEARCH_TERMINATION_STRATEGY_T{});