📄 page549.html
字号:
<HTML><HEAD><TITLE>Depth-First Traversal</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="tex2html7474" HREF="page550.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7472" HREF="page548.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7466" HREF="page548.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7476" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0016310000000000000000">Depth-First Traversal</A></H2><P>The <em>depth-first traversal</em><A NAME=49909> </A><A NAME=49910> </A>of a graph is likethe depth-first traversal of a tree discussed in Section <A HREF="page258.html#sectreestraversals"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.A depth-first traversal of a tree always starts at the root of the tree.Since a graph has no root,when we do a depth-first traversal,we must specify the vertex at which to begin.<P>A depth-first traversal of a tree visits a nodeand then recursively visits the subtrees of that node.Similarly, depth-first traversal of a graph visits a vertexand then recursively visits all the vertices adjacent to that node.The catch is that the graph may contain cycles,but the traversal must visit every vertex at most once.The solution to the problem isto keep track of the nodes that have been visited,so that the traversal does not suffer the fate of infinite recursion.<P><P><A NAME="50193"> </A><A NAME="figgraph6"> </A> <IMG WIDTH=575 HEIGHT=183 ALIGN=BOTTOM ALT="figure49912" SRC="img2285.gif" ><BR><STRONG>Figure:</STRONG> Depth-first traversal.<BR><P><P>For example, Figure <A HREF="page549.html#figgraph6"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates the depth-first traversalof the directed graph <IMG WIDTH=17 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline70643" SRC="img2182.gif" > starting from vertex <I>c</I>.The depth-first traversal visits the nodes in the order<P> <IMG WIDTH=277 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath71169" SRC="img2286.gif" ><P>A depth-first traversal only follows edges that lead to unvisited vertices.As shown in Figure <A HREF="page549.html#figgraph6"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,if we omit the edges that are not followed,the remaining edges form a tree.Clearly, the depth-first traversal of this treeis equivalent to the depth-first traversal of the graph<P><BR> <HR><UL> <LI> <A NAME="tex2html7477" HREF="page550.html#SECTION0016311000000000000000">Implementation</A><LI> <A NAME="tex2html7478" HREF="page551.html#SECTION0016312000000000000000">Running Time Analysis</A></UL><HR><A NAME="tex2html7474" HREF="page550.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7472" HREF="page548.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7466" HREF="page548.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7476" 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 + -