Struct petgraph::visit::Bfs

pub struct Bfs<N, VM> {
    pub stack: VecDeque<N>,
    pub discovered: VM,
}

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

Methods

impl<N, VM> Bfs<N, VM> where N: Copy, VM: VisitMap<N>

fn new<G>(graph: G, start: N) -> Self where G: GraphRef + 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<G>(&mut self, graph: G) -> Option<N> where G: IntoNeighbors<NodeId=N>

Return the next node in the dfs, or None if the traversal is done.

Trait Implementations

impl<N: Clone, VM: Clone> Clone for Bfs<N, VM>

fn clone(&self) -> Bfs<N, VM>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.