pub struct Bfs<N, VM> {
pub stack: VecDeque<N>,
pub discovered: VM,
}
Expand description
A breadth first search (BFS) of a graph.
The traversal starts at a given node and only traverses nodes reachable from it.
Bfs
is not recursive.
Bfs
does not itself borrow the graph, and because of this 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;
use petgraph::visit::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
Implementations§
source§impl<N, VM> Bfs<N, VM>
impl<N, VM> Bfs<N, VM>
Trait Implementations§
Auto Trait Implementations§
impl<N, VM> Freeze for Bfs<N, VM>where
VM: Freeze,
impl<N, VM> RefUnwindSafe for Bfs<N, VM>where
VM: RefUnwindSafe,
N: RefUnwindSafe,
impl<N, VM> Send for Bfs<N, VM>
impl<N, VM> Sync for Bfs<N, VM>
impl<N, VM> Unpin for Bfs<N, VM>
impl<N, VM> UnwindSafe for Bfs<N, VM>where
VM: UnwindSafe,
N: UnwindSafe,
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more
source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
source§default unsafe fn clone_to_uninit(&self, dst: *mut T)
default unsafe fn clone_to_uninit(&self, dst: *mut T)
🔬This is a nightly-only experimental API. (
clone_to_uninit
)