page562.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 71 行
HTML
71 行
<HTML><HEAD><TITLE>Testing for Cycles in a Directed Graph</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="tex2html7617" HREF="page563.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7615" HREF="page558.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7611" HREF="page561.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7619" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0016344000000000000000">Testing for Cycles in a Directed Graph</A></H3><P>The final application of graph traversalthat we consider in this sectionis to test a directed graph for cycles.An easy way to do this is to attempt a topological-order traversalusing the algorithm given in Section <A HREF="page555.html#secgraphstoposort"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.This algorithm only visits all the vertices of a directed graphif that graph contains no cycles.<P>To see why this is so,consider the directed cyclic graph <IMG WIDTH=25 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71375" SRC="img2327.gif" > shown in Figure <A HREF="page562.html#figgraph11"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The topological traversal algorithm beginsby computing the <em>in-degrees</em> of the vertices.(The number shown below each vertex in Figure <A HREF="page562.html#figgraph11"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>is the in-degree of that vertex).<P><P><A NAME="51307"> </A><A NAME="figgraph11"> </A> <IMG WIDTH=575 HEIGHT=101 ALIGN=BOTTOM ALT="figure51148" SRC="img2328.gif" ><BR><STRONG>Figure:</STRONG> A directed cyclic graph.<BR><P><P>At each step of the traversal,a vertex with in-degree of zero is visited.After a vertex is visited,the vertex and all the edges emanating from that vertexare removed from the graph.Notice that if we remove vertex <I>a</I> and edge (<I>a</I>,<I>b</I>) from <IMG WIDTH=25 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71375" SRC="img2327.gif" >,all the remaining vertices have in-degrees of one.The presence of the cycle preventsthe topological-order traversal from completing.<P>Therefore, the a simple way to test whether a directed graph is cyclicis to attempt a topological traversal of its vertices.If all the vertices are not visited,the graph must be cyclic.<P>Program <A HREF="page562.html#progdigraphd"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the implementation of the <tt>getIsCyclic</tt>method of the <tt>Digraph</tt> class.This method returns <tt>True</tt> if the graph is cyclic.The implementation uses a visitor that countsthe number of vertices visited during a<tt>topologicalOrderTraversal</tt> of the graph.<P><P><A NAME="51366"> </A><A NAME="progdigraphd"> </A> <IMG WIDTH=575 HEIGHT=161 ALIGN=BOTTOM ALT="program51316" SRC="img2329.gif" ><BR><STRONG>Program:</STRONG> Abstract <tt>Digraph</tt> class <tt>getIsCyclic</tt> method.<BR><P><P>The worst-case running time of the <tt>getIsCyclic</tt> methodis determined by the time taken by the <tt>topologicalOrderTraversal</tt>.Since <IMG WIDTH=108 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60707" SRC="img668.gif" >,the running time of <tt>getIsCyclic</tt> is <IMG WIDTH=50 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline70923" SRC="img2242.gif" > when adjacency matrices are used to represent the graphand <IMG WIDTH=81 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71119" SRC="img2282.gif" > when adjacency lists are used.<P><HR><A NAME="tex2html7617" HREF="page563.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7615" HREF="page558.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7611" HREF="page561.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7619" 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 + =
减小字号Ctrl + -
显示快捷键?