📄 page554.html
字号:
<HTML>
<HEAD>
<TITLE>Breadth-First Traversal</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html8761" HREF="page555.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page555.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html8759" HREF="page550.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page550.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html8753" HREF="page553.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page553.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html8763" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html8764" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H2><A NAME="SECTION0017320000000000000000">Breadth-First Traversal</A></H2>
<P>
The <em>breadth-first traversal</em><A NAME=50335> </A><A NAME=50336> </A>
of a graph is like
the breadth-first traversal of a tree discussed in Section <A HREF="page257.html#sectreestraversals" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page257.html#sectreestraversals"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
The breadth-first traversal of a tree visits the nodes
in the order of their depth in the tree.
Breadth-first tree traversal first visits all the nodes at depth zero
(i.e., the root),
then all the nodes at depth one, and so on.
<P>
Since a graph has no root,
when we do a breadth-first traversal,
we must specify the vertex at which to start the traversal.
Furthermore, we can define the depth of a given vertex to be the length
of the shortest path from the starting vertex to the given vertex.
Thus, breadth-first traversal first visits the starting vertex,
then all the vertices adjacent to the starting vertex,
and the all the vertices adjacent to those, and so on.
<P>
Section <A HREF="page156.html#secqueuesapps" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page156.html#secqueuesapps"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> presents a non-recursive
breadth-first traversal algorithm for <I>N</I>-ary trees
that uses a queue to keep track vertices that need to be visited.
The breadth-first graph traversal algorithm is very similar.
<P>
First, the starting vertex is enqueued.
Then, the following steps are repeated until the queue is empty:
<OL><LI> Remove the vertex at the head of the queue and call it <tt>vertex</tt>.<LI> Visit <tt>vertex</tt>.<LI> Follow each edge emanating from <tt>vertex</tt>
to find the adjacent vertex and call it <tt>to</tt>.
If <tt>to</tt> has not already been put into the queue, enqueue it.
</OL>
Notice that a vertex can be put into the queue at most once.
Therefore, the algorithm must somehow keep track of the vertices
that have been enqueued.
<P>
<P><A NAME="50520"> </A><A NAME="figgraph7"> </A> <IMG WIDTH=575 HEIGHT=272 ALIGN=BOTTOM ALT="figure50346" SRC="img2402.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2402.gif" ><BR>
<STRONG>Figure:</STRONG> Breadth-First Traversal<BR>
<P>
<P>
Figure <A HREF="page554.html#figgraph7" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page554.html#figgraph7"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> illustrates the breadth-first traversal
of the directed graph <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71449" SRC="img2298.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2298.gif" > starting from vertex <I>a</I>.
The algorithm begins by inserting the starting vertex, <I>a</I>,
into the empty queue.
Next, the head of the queue (vertex <I>a</I>) is dequeued and visited,
and the vertices adjacent to it (vertices <I>b</I> and <I>c</I>) are enqueued.
When, <I>b</I> is dequeued and visited
we find that there is only adjacent vertex, <I>c</I>,
and that vertex is already in the queue.
Next vertex <I>c</I> is dequeued and visited.
Vertex <I>c</I> is adjacent to <I>a</I> and <I>d</I>.
Since <I>a</I> has already been enqueued (and subsequently dequeued)
only vertex <I>d</I> is put into the queue.
Finally, vertex <I>d</I> is dequeued an visited.
Therefore, the breadth-first traversal of <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71449" SRC="img2298.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2298.gif" > starting from <I>a</I>
visits the vertices in the sequence
<P> <IMG WIDTH=278 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath71991" SRC="img2403.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2403.gif" ><P><BR> <HR>
<UL>
<LI> <A NAME="tex2html8765" HREF="page555.html#SECTION0017321000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page555.html#SECTION0017321000000000000000">Implementation</A>
<LI> <A NAME="tex2html8766" HREF="page556.html#SECTION0017322000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page556.html#SECTION0017322000000000000000">Running Time Analysis</A>
</UL>
<HR><A NAME="tex2html8761" HREF="page555.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page555.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html8759" HREF="page550.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page550.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html8753" HREF="page553.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page553.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html8763" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html8764" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -