class RGL::BFSIterator

File traversal.rb defines the basic graph traversal algorithm for DFS and BFS search. They are implemented as a {GraphIterator}, which is a Stream of vertices of a given graph. The streams are not reversable.

Beside being an iterator in the sense of the Stream mixin, {BFSIterator} and {DFSIterator} follow the {www.boost.org/libs/graph/doc/visitor_concepts.html BGL Visitor Concepts} in a slightly modified fashion (especially for the {DFSIterator}).

A {BFSIterator} can be used to traverse a graph from a given start vertex in breath first search order. Since the iterator also mixins the {GraphVisitor}, it provides all event points defined there.

The vertices which are not yet visited are held in the queue +@waiting+. During the traversal, vertices are colored using the colors :GRAY (when waiting) and :BLACK when finished. All other vertices are :WHITE.

For more see the BGL BFS Visitor Concept.

See the implementation of {Graph#bfs_search_tree_from} for an example usage.

@see Graph#bfs_iterator @see Graph#bfs_search_tree_from