Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/breadth_first_search.html @ 45

Last change on this file since 45 was 29, checked in by landauf, 16 years ago

updated boost from 1_33_1 to 1_34_1
File size: 11.2 KB
Line 
1<HTML>
2<!--
3  -- Copyright (c) Jeremy Siek 2000, 2001
4  --
5  -- Distributed under the Boost Software License, Version 1.0.
6  -- (See accompanying file LICENSE_1_0.txt or copy at
7  -- http://www.boost.org/LICENSE_1_0.txt)
8  -->
9<Head>
10<Title>Boost Graph Library: Breadth-First Search</Title>
11<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
12        ALINK="#ff0000"> 
13<IMG SRC="../../../boost.png" 
14     ALT="C++ Boost" width="277" height="86"> 
15
16<BR Clear>
17
18<H1><A NAME="sec:bfs">
19<img src="figs/python.gif" alt="(Python)"/>
20<TT>breadth_first_search</TT>
21</H1>
22
23<P>
24<PRE>
25<i>// named parameter version</i>
26template &lt;class Graph, class P, class T, class R&gt;
27void breadth_first_search(Graph& G,
28  typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
29  const bgl_named_params&lt;P, T, R&gt;&amp; params);
30
31<i>// non-named parameter version</i>
32template &lt;class Graph, class Buffer, class BFSVisitor,
33          class ColorMap&gt;
34void breadth_first_search(const Graph&amp; g,
35   typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
36   Buffer&amp; Q, BFSVisitor vis, ColorMap color);
37</PRE>
38
39
40<p>
41The <tt>breadth_first_search()</tt> function performs a breadth-first
42traversal [<a href="./bibliography.html#moore59">49</a>] of a directed
43or undirected graph.  A breadth-first traversal visits vertices that
44are closer to the source before visiting vertices that are further
45away. In this context ``distance'' is defined as the number of edges
46in the shortest path from the source vertex. The
47<tt>breadth_first_search()</tt> function can be used to compute the
48shortest path from the source to all reachable vertices and the
49resulting shortest-path distances. For more definitions related to BFS
50see section <a href="./graph_theory_review.html#sec:bfs-algorithm">
51Breadth-First Search</a>.
52</p>
53
54<p>
55BFS uses two data structures to to implement the traversal: a color
56marker for each vertex and a queue. White vertices are undiscovered
57while gray vertices are discovered but have undiscovered adjacent
58vertices. Black vertices are discovered and are adjacent to only other
59black or gray vertices.  The algorithm proceeds by removing a vertex
60</i>u</i> from the queue and examining each out-edge <i>(u,v)</i>. If an
61adjacent vertex <i>v</i> is not already discovered, it is colored gray and
62placed in the queue. After all of the out-edges are examined, vertex
63<i>u</i> is colored black and the process is repeated.  Pseudo-code for the
64BFS algorithm is a listed below.
65</p>
66
67<table>
68<tr>
69<td valign="top">
70<pre>
71BFS(<i>G</i>, <i>s</i>)
72  <b>for</b> each vertex <i>u in V[G]</i>
73    <i>color[u] :=</i> WHITE
74    <i>d[u] := infinity</i> 
75    <i>p[u] := u</i> 
76  <b>end for</b>
77  <i>color[s] :=</i> GRAY
78  <i>d[s] := 0</i> 
79  ENQUEUE(<i>Q</i>, <i>s</i>)
80  <b>while</b> (<i>Q != &Oslash;</i>)
81    <i>u :=</i> DEQUEUE(Q)
82    <b>for</b> each vertex <i>v in Adj[u]</i>
83      <b>if</b> (<i>color[v] =</i> WHITE)
84        <i>color[v] :=</i> GRAY
85        <i>d[v] := d[u] + 1</i> 
86        <i>p[v] := u</i> 
87        ENQUEUE(<i>Q</i>, <i>v</i>)
88      <b>else</b>
89        <b>if</b> (<i>color[v] =</i> GRAY)
90          ...
91        <b>else</b> 
92          ...
93    <b>end for</b>
94    <i>color[u] :=</i> BLACK
95  <b>end while</b>
96  return (<i>d</i>, <i>p</i>)
97</pre>
98</td>
99<td valign="top">
100<pre>
101
102initialize vertex <i>u</i> 
103
104
105
106
107
108
109discover vertex <i>s</i> 
110
111examine vertex <i>u</i> 
112examine edge <i>(u,v)</i>
113<i>(u,v)</i> is a tree edge
114
115
116
117discover vertex <i>v</i> 
118<i>(u,v)</i> is a non-tree edge
119
120<i>(u,v)</i> has a gray target
121
122<i>(u,v)</i> has a black target
123
124finish vertex <i>u</i> 
125</pre>
126</tr>
127</table>
128
129The <tt>breadth_first_search()</tt> function can be extended with
130user-defined actions that will be called a certain event points. The
131actions must be provided in the form of a visitor object, that is, an
132object who's type meets the requirements for a <a
133href="./BFSVisitor.html">BFS Visitor</a>. In the above pseudo-code,
134the event points are the labels on the right. Also a description of
135each event point is given below. By default, the
136<tt>breadth_first_search()</tt> function does not carry out any
137actions, not even recording distances or predecessors. However these
138can be easily added using the <a
139href="./distance_recorder.html"><tt>distance_recorder</tt></a> and <a
140href="./predecessor_recorder.html"><tt>predecessor_recorder</tt></a>
141event visitors.
142
143
144<H3>Where Defined</H3>
145
146<P>
147<a href="../../../boost/graph/breadth_first_search.hpp"><TT>boost/graph/breadth_first_search.hpp</TT></a>
148
149<P>
150
151<h3>Parameters</h3>
152
153IN: <tt>Graph&amp; g</tt>
154<blockquote>
155  A directed or undirected graph. The graph type must
156  be a model of <a href="./VertexListGraph.html">Vertex List Graph</a>
157  and <a href="./IncidenceGraph.html">Incidence Graph</a>.<br>
158
159  <b>Python</b>: The parameter is named <tt>graph</tt>.
160</blockquote>
161
162IN: <tt>vertex_descriptor s</tt>
163<blockquote>
164  The source vertex where the search is started.<br>
165
166  <b>Python</b>: The parameter is named <tt>root_vertex</tt>.
167</blockquote>
168
169
170<h3>Named Parameters</h3>
171
172IN: <tt>visitor(BFSVisitor vis)</tt>
173<blockquote>
174  A visitor object that is invoked inside the algorithm at the
175  event-points specified by the <a href="BFSVisitor.html">BFS
176  Visitor</a> concept. The visitor object is passed by value <a
177  href="#1">[1]</a>.<br> <b>Default:</b>
178  <tt>bfs_visitor&lt;null_visitor&gt;</tt> <br>
179
180  <b>Python</b>: The parameter should be an object that derives from
181  the <a href="BFSVisitor.html#python"><tt>BFSVisitor</tt></a> type of the graph.
182
183</blockquote>
184
185UTIL/OUT: <tt>color_map(ColorMap color)</tt>
186<blockquote>
187  This is used by the algorithm to keep track of its progress through
188  the graph. The user need not initialize the color map before calling
189  <tt>breadth_first_search()</tt> since the algorithm initializes the
190  color of every vertex to white at the start of the algorihtm. If you
191  need to perform multiple breadth-first searches on a graph (for
192  example, if there are some disconnected components) then use the <a
193  href="./breadth_first_visit.html"><tt>breadth_first_visit()</tt></a>
194  function and do your own color initialization.
195
196  <p>The type <tt>ColorMap</tt> must be a model of <a
197  href="../../property_map/ReadWritePropertyMap.html">Read/Write
198  Property Map</a> and its key type must be the graph's vertex
199  descriptor type and the value type of the color map must model
200  <a href="./ColorValue.html">ColorValue</a>.<br>
201  <b>Default:</b> an <a
202  href="../../property_map/iterator_property_map.html">
203  </tt>iterator_property_map</tt></a> created from a
204  <tt>std::vector</tt> of <tt>default_color_type</tt> of size
205  <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
206  map.<br>
207
208  <b>Python</b>: The color map must be a <tt>vertex_color_map</tt> for
209  the graph.
210</blockquote>
211
212IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
213<blockquote>
214  This maps each vertex to an integer in the range <tt>[0,
215  num_vertices(g))</tt>. This parameter is only necessary when the
216  default color property map is used. The type <tt>VertexIndexMap</tt>
217  must be a model of <a
218  href="../../property_map/ReadablePropertyMap.html">Readable Property
219  Map</a>. The value type of the map must be an integer type. The
220  vertex descriptor type of the graph needs to be usable as the key
221  type of the map.<br>
222
223  <b>Default:</b> <tt>get(vertex_index, g)</tt>.
224    Note: if you use this default, make sure your graph has
225    an internal <tt>vertex_index</tt> property. For example,
226    <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
227    not have an internal <tt>vertex_index</tt> property.<br>
228
229  <b>Python</b>: Unsupported parameter.
230</blockquote>
231
232UTIL: <tt>buffer(Buffer&amp; Q)</tt>
233<blockquote>
234  The queue used to determine the order in which vertices will be
235  discovered.  If a FIFO queue is used, then the traversal will
236  be according to the usual BFS ordering. Other types of queues
237  can be used, but the traversal order will be different.
238  For example Dijkstra's algorithm can be implemented
239  using a priority queue. The type <tt>Buffer</tt> must be a model of
240  <a href="./Buffer.html">Buffer</a>.<br> The <tt>value_type</tt>
241  of the buffer must be the <tt>vertex_descriptor</tt> type for the graph.<br>
242  <b>Default:</b> <tt>boost::queue</tt><br>
243
244  <b>Python</b>: The buffer must derive from the <a
245  href="./Buffer.html">Buffer</a> type for the graph.
246
247</blockquote> 
248
249
250<H3><A NAME="SECTION001330300000000000000">
251Complexity</A>
252</H3>
253
254<P>
255The time complexity is <i>O(E + V)</i>.
256
257<P>
258
259<h3>Visitor Event Points</h3>
260
261<ul>
262<li><b><tt>vis.initialize_vertex(v, g)</tt></b> is invoked on every vertex
263  before the start of the search.
264
265<li><b><tt>vis.examine_vertex(u, g)</tt></b>r is invoked in each
266  vertex as it is removed from the queue.
267
268<li><b><tt>vis.examine_edge(e, g)</tt></b> is invoked on every out-edge
269  of each vertex immediately after the vertex is removed from the queue.
270
271<li><b><tt>vis.tree_edge(e, g)</tt></b> is invoked (in addition to
272  <tt>examine_edge()</tt>) if the edge is a tree edge. The
273  target vertex of edge <tt>e</tt> is discovered at this time.
274
275<li><b><tt>vis.discover_vertex(u, g)</tt></b> is invoked the first time the
276  algorithm encounters vertex <i>u</i>. All vertices closer to the
277  source vertex have been discovered, and vertices further from the
278  source have not yet been discovered.
279
280<li><b><tt>vis.non_tree_edge(e, g)</tt></b> is invoked (in addition to
281  <tt>examine_edge()</tt>) if the edge is not a tree edge.
282
283<li><b><tt>vis.gray_target(e, g)</tt></b> is invoked (in addition to
284  <tt>non_tree_edge()</tt>) if the target vertex is colored gray at the
285  time of examination. The color gray indicates that
286  the vertex is currently in the queue.
287
288<li><b><tt>vis.black_target(e, g)</tt></b> is invoked (in addition to
289  <tt>non_tree_edge()</tt>) if the target vertex is colored black at the
290  time of examination. The color black indicates that the
291  vertex is no longer in the queue.
292
293<li><b><tt>vis.finish_vertex(u, g)</tt></b> is invoked after all of the out
294  edges of <i>u</i> have been examined and all of the adjacent vertices
295  have been discovered.
296
297</ul>
298
299<H3><A NAME="SECTION001330400000000000000">
300Example</A>
301</H3>
302
303<P>
304The example in <a
305href="../example/bfs-example.cpp"><TT>example/bfs-example.cpp</TT></a>
306demonstrates using the BGL Breadth-first search algorithm on the graph
307from <A HREF="./graph_theory_review.html#fig:bfs-example">Figure
3085</A>. The file
309<a href="../example/bfs-example2.cpp"><TT>example/bfs-example2.cpp</TT></a>
310contains the same example, except that the <tt>adacency_list</tt>
311class used has <tt>VertexList</tt> and <tt>EdgeList</tt> set
312to <tt>listS</tt>.
313</P>
314
315<h3>See Also</h3>
316
317<a href="./bfs_visitor.html"><tt>bfs_visitor</tt></a> and
318<a href="./depth_first_search.html"><tt>depth_first_search()</tt></a>
319
320<h3>Notes</h3>
321
322<p><a name="1">[1]</a> 
323  Since the visitor parameter is passed by value, if your visitor
324  contains state then any changes to the state during the algorithm
325  will be made to a copy of the visitor object, not the visitor object
326  passed in. Therefore you may want the visitor to hold this state by
327  pointer or reference.
328
329<br>
330<HR>
331<TABLE>
332<TR valign=top>
333<TD nowrap>Copyright &copy 2000-2001</TD><TD>
334<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
335</TD></TR></TABLE>
336
337</BODY>
338</HTML> 
Note: See TracBrowser for help on using the repository browser.