Definition
An instance algorithm of class GIT_BFS< OutAdjIt, Queuetype, Mark > is an implementation of an algorithm that traverses a graph in a breadth first order. The queue used for the search must be provided by the caller and contains the source(s) of the search.
Iterator version: There is an iterator version of this algorithm: BFS_It. Usage is similar to that of node iterators without the ability to go backward in the sequence.
#include < LEDA/graph/graph_iterator.h >
Creation
GIT_BFS< OutAdjIt, Queuetype, Mark > | algorithm(const Queuetype& q, Mark& ma) | |
creates an instance algorithm of this class bound to the Queue q and data accessor ma. |
Preconditions:
GIT_BFS< OutAdjIt, Queuetype, Mark > | algorithm(const Queuetype& q, Mark& ma, const OutAdjIt& ai) | |
creates an instance algorithm of this class bound to the queue q, data accessor ma and the adjacency iterator ai representing the source node of the breadth first traversal. |
Operations
void | algorithm.next() | Performs one iteration of the core loop of the algorithm. |
OutAdjIt | algorithm.current() | returns the ``current'' iterator. |
void | algorithm.finish_algo() | executes the algorithm until finished() is true, i.e. exactly if the Queue is empty. |
bool | algorithm.finished() | returns true if the internal Queue is empty. |
Queuetype& | algorithm.get_queue() | gives direct access to internal Queue. |
Example
This example shows how to implement an algorithmic iterator for breadth first search:
class BFS_It { AdjIt _source; node_array<da> _handler; node_array_da<bool> _mark; queue<AdjIt> _q; GIT_BFS<AdjIt,queue<AdjIt>,node_array_da<bool> > _search; public: BFS_It(graph& G) : _source(AdjIt(G)), _handler(G,false), _mark(_handler), _search(_q,_mark) { _search.get_queue().clear(); _search.get_queue().append(_source); } bool valid() const { return !_search.finished(); } node get_node() const { return _search.current().get_node(); } BFS_It& operator++() { _search.next(); return *this; } };
With this iterator you can easily iterate through a graph in breadth first fashion :
graph G; BFS_It it(G); while (it.valid()) { // do something reasonable with 'it.get_node()' ++it; }
Implementation
Each operation requires constant time. Therefore, a normal breadth-first search needs (m + n) time.