Class DepthFirstPaths

src/graph/util/paths.rs:21–25

Run depth-first search on an undirected graph. Determine reachability in a digraph from a given vertex using depth-first search. Runs in O(E + V) time.

/// depth-first search.
/// Runs in O(E + V) time.
pub struct DepthFirstPaths {
    marked: Vec<bool>,   // marked[v] = is there an s-v path?
    edge_to: Vec<usize>, // edgeTo[v] = last edge on s-v path
    s: usize,            // source vertex
}

/// Run breadth first search on an undirected graph.
/// Runs in O(E + V) time.