Class BreadthFirstPaths

src/graph/util/paths.rs:32–37

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

/// Run breadth-first search on a digraph.
/// Runs in O(E + V) time.
pub struct BreadthFirstPaths {
    marked: Vec<bool>,   // marked[v] = is there an s-v path
    edge_to: Vec<usize>, // edgeTo[v] = previous edge on shortest s-v path
    dist_to: Vec<usize>, // distTo[v] = number of edges shortest s-v path
    s: usize,            // source vertex
}

impl Paths for DepthFirstPaths {
    fn has_path(&self, v: usize) -> bool {