Struct petgraph::visit::Bfs [] [src]

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

The queue of nodes to visit

The map of discovered nodes

Methods

impl<N, VM> Bfs<N, VM> where
    N: Copy + PartialEq,
    VM: VisitMap<N>, 
[src]

[src]

Create a new Bfs, using the graph's visitor map, and put start in the stack of nodes to visit.

[src]

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

Trait Implementations

impl<N: Clone, VM: Clone> Clone for Bfs<N, VM>
[src]

[src]

Returns a copy of the value. Read more

1.0.0
[src]

Performs copy-assignment from source. Read more

impl<G> Walker<G> for Bfs<G::NodeId, G::Map> where
    G: IntoNeighbors + Visitable
[src]

[src]

Advance to the next item

Important traits for WalkerIter<W, C>
[src]

Create an iterator out of the walker and given context.