...one of the most highly
regarded and expertly designed C++ library projects in the
world. — Herb Sutter and Andrei
// named parameter version template <class Graph, class P, class T, class R> void breadth_first_search(Graph& G, typename graph_traits<Graph>::vertex_descriptor s, const bgl_named_params<P, T, R>& params); // non-named parameter version template <class Graph, class Buffer, class BFSVisitor, class ColorMap> void breadth_first_search(const Graph& g, typename graph_traits<Graph>::vertex_descriptor s, Buffer& Q, BFSVisitor vis, ColorMap color);
The breadth_first_search() function performs a breadth-first traversal  of a directed or undirected graph. A breadth-first traversal visits vertices that are closer to the source before visiting vertices that are further away. In this context ``distance'' is defined as the number of edges in the shortest path from the source vertex. The breadth_first_search() function can be used to compute the shortest path from the source to all reachable vertices and the resulting shortest-path distances. For more definitions related to BFS see section Breadth-First Search.
BFS uses two data structures to to implement the traversal: a color marker for each vertex and a queue. White vertices are undiscovered while gray vertices are discovered but have undiscovered adjacent vertices. Black vertices are discovered and are adjacent to only other black or gray vertices. The algorithm proceeds by removing a vertex u from the queue and examining each out-edge (u,v). If an adjacent vertex v is not already discovered, it is colored gray and placed in the queue. After all of the out-edges are examined, vertex u is colored black and the process is repeated. Pseudo-code for the BFS algorithm is a listed below.
BFS(G, s) for each vertex u in V[G] color[u] := WHITE d[u] := infinity p[u] := u end for color[s] := GRAY d[s] := 0 ENQUEUE(Q, s) while (Q != Ø) u := DEQUEUE(Q) for each vertex v in Adj[u] if (color[v] = WHITE) color[v] := GRAY d[v] := d[u] + 1 p[v] := u ENQUEUE(Q, v) else if (color[v] = GRAY) ... else ... end for color[u] := BLACK end while return (d, p)
initialize vertex u discover vertex s examine vertex u examine edge (u,v) (u,v) is a tree edge discover vertex v (u,v) is a non-tree edge (u,v) has a gray target (u,v) has a black target finish vertex u
A directed or undirected graph. The graph type must be a model of Vertex List Graph and Incidence Graph.IN: vertex_descriptor s
Python: The parameter is named graph.
The source vertex where the search is started.
Python: The parameter is named root_vertex.
A visitor object that is invoked inside the algorithm at the event-points specified by the BFS Visitor concept. The visitor object is passed by value .UTIL/OUT: color_map(ColorMap color)
Python: The parameter should be an object that derives from the BFSVisitor type of the graph.
This is used by the algorithm to keep track of its progress through the graph. The user need not initialize the color map before calling breadth_first_search() since the algorithm initializes the color of every vertex to white at the start of the algorihtm. If you need to perform multiple breadth-first searches on a graph (for example, if there are some disconnected components) then use the breadth_first_visit() function and do your own color initialization.IN: vertex_index_map(VertexIndexMap i_map)
The type ColorMap must be a model of Read/Write Property Map and its key type must be the graph's vertex descriptor type and the value type of the color map must model ColorValue.
Default: an iterator_property_map created from a std::vector of default_color_type of size num_vertices(g) and using the i_map for the index map.
Python: The color map must be a vertex_color_map for the graph.
This maps each vertex to an integer in the range [0, num_vertices(g)). This parameter is only necessary when the default color property map is used. The type VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.UTIL: buffer(Buffer& Q)
Default: get(vertex_index, g). Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacency_list with VertexList=listS does not have an internal vertex_index property.
Python: Unsupported parameter.
The queue used to determine the order in which vertices will be discovered. If a FIFO queue is used, then the traversal will be according to the usual BFS ordering. Other types of queues can be used, but the traversal order will be different. For example Dijkstra's algorithm can be implemented using a priority queue. The type Buffer must be a model of Buffer.
The value_type of the buffer must be the vertex_descriptor type for the graph.
Python: The buffer must derive from the Buffer type for the graph.
The time complexity is O(E + V).
The example in example/bfs-example.cpp demonstrates using the BGL Breadth-first search algorithm on the graph from Figure 6. The file example/bfs-example2.cpp contains the same example, except that the adacency_list class used has VertexList and EdgeList set to listS.
Since the visitor parameter is passed by value, if your visitor
contains state then any changes to the state during the algorithm
will be made to a copy of the visitor object, not the visitor object
passed in. Therefore you may want the visitor to hold this state by
pointer or reference.
|Copyright © 2000-2001||Jeremy Siek, Indiana University (firstname.lastname@example.org)|