Struct daggy::petgraph::visit::Bfs
[−]
[src]
pub struct Bfs<N, VM> { pub stack: VecDeque<N>, pub discovered: VM, }
A breadth first search (BFS) of a graph.
Using a Bfs you can run a traversal over a graph while still retaining mutable access to it, if you use it like the following example:
use petgraph::{Graph, Bfs}; let mut graph = Graph::<_,()>::new(); let a = graph.add_node(0); let mut bfs = Bfs::new(&graph, a); while let Some(nx) = bfs.next(&graph) { // we can access `graph` mutably here still graph[nx] += 1; } assert_eq!(graph[a], 1);
Note: The algorithm may not behave correctly if nodes are removed during iteration. It may not necessarily visit added nodes or edges.
Fields
stack: VecDeque<N>
The queue of nodes to visit
discovered: VM
The map of discovered nodes
Methods
impl<N, VM> Bfs<N, VM> where N: Clone, VM: VisitMap<N>
fn new<G>(graph: &G, start: N) -> Bfs<N, VM> where G: Visitable<NodeId=N, Map=VM>
[−]
Create a new Bfs, using the graph's visitor map, and put start in the stack of nodes to visit.
fn next<'a, G>(&mut self, graph: &'a G) -> Option<N> where G: Graphlike<NodeId=N> + NeighborIter<'a>
[−]
Return the next node in the dfs, or None if the traversal is done.