📄 page574.html
字号:
<HTML><HEAD><TITLE>Constructing Spanning Trees</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html7756" HREF="page575.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7754" HREF="page573.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7748" HREF="page573.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7758" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0016501000000000000000">Constructing Spanning Trees</A></H3><P>Any traversal of a connected, undirected treevisits all the vertices in that tree,regardless of the node from which the traversal is started.During the traversal certain edges are traversedwhile the remaining edges are not.Specifically, an edge is traversed if it leads from a vertexthat has been visited to a vertex that has not been visited.The set of edges which are traversed during a traversalforms a spanning tree.<P>The spanning tree obtained from a breadth-first traversalstarting at vertex <I>v</I> of graph <I>G</I>is called the <em>breadth-first spanning tree</em><A NAME=52495> </A><A NAME=52496> </A>of <I>G</I> rooted at <I>v</I>.For example, the spanning tree shown in Figure <A HREF="page573.html#figgraph15"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (c)is the breadth-first spanning tree of <IMG WIDTH=25 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline72025" SRC="img2407.gif" > rooted at vertex <I>b</I>.<P>Similarly, the spanning tree obtained from a depth-firsttraversal is the <em>depth-first spanning tree</em><A NAME=52500> </A><A NAME=52501> </A>of <I>G</I> rooted at <I>v</I>.The spanning tree shown in Figure <A HREF="page573.html#figgraph15"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (d)is the depth-first spanning tree of <IMG WIDTH=25 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline72025" SRC="img2407.gif" > rooted at vertex <I>c</I>.<P><HR><A NAME="tex2html7756" HREF="page575.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7754" HREF="page573.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7748" HREF="page573.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7758" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -