page547.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 113 行
HTML
113 行
<HTML><HEAD><TITLE>Time Comparison</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="tex2html7448" HREF="page548.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7446" HREF="page545.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7442" HREF="page546.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7450" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0016282000000000000000">Time Comparison</A></H3><P>The following four operations are used extensively in the implementationsof many different graph algorithms:<DL ><DT><STRONG>find edge (<I>v</I>,<I>w</I>)</STRONG><DD> Given vertices <I>v</I> and <I>w</I>, this operation locates the corresponding <tt>Edge</tt> instance. When using an adjacency matrix, we can find an edge in constant time.<P> When adjacency lists are used, the worst-case running time is <IMG WIDTH=65 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71105" SRC="img2280.gif" >, since <IMG WIDTH=40 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71107" SRC="img2281.gif" > is the length of the adjacency list associated with vertex <I>v</I>.<P> This is the operation performed by the <tt>getEdge</tt> method of the <tt>Graph</tt> interface.<P> <DT><STRONG>enumerate all edges</STRONG><DD> In order to locate all the edges in when using adjacency matrices, it is necessary to examine all <IMG WIDTH=25 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline70835" SRC="img2228.gif" > matrix entries. Therefore, the worst-case running time needed to enumerate all the edges is <IMG WIDTH=50 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline70923" SRC="img2242.gif" >.<P> On the other hand, to enumerate all the edges when using adjacency lists requires the traversal of <IMG WIDTH=18 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70975" SRC="img2249.gif" > lists. In all there are <IMG WIDTH=17 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70987" SRC="img2251.gif" > edges. Therefore the worst case running time is <IMG WIDTH=81 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71119" SRC="img2282.gif" >.<P> This operation is performed using the enumerator obtained using the <tt>edges</tt> property of the <tt>Graph</tt> interface.<P> <DT><STRONG>enumerate edges emanating from <I>v</I></STRONG><DD> To enumerate all the edges that emanate from vertex <I>v</I> requires a complete scan of the <IMG WIDTH=20 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline71125" SRC="img2283.gif" > row of an adjacency matrix. Therefore, the worst-case running time when using adjacency matrices is <IMG WIDTH=43 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70999" SRC="img2255.gif" >.<P> Enumerating the edges emanating from vertex <I>v</I> is a trivial operation when using adjacency lists. All we need do is traverse the <IMG WIDTH=20 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline71125" SRC="img2283.gif" > list. This takes <IMG WIDTH=65 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71105" SRC="img2280.gif" > time in the worst case.<P> This operation is performed using the enumerator obtained using the <tt>getEmanatingEdges</tt> property of the <tt>Vertex</tt> interface.<P> <DT><STRONG>enumerate edges incident on <I>w</I></STRONG><DD> To enumerate all the edges are incident on vertex <I>w</I> requires a complete scan of the <IMG WIDTH=23 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline71139" SRC="img2284.gif" > column of an adjacency matrix. Therefore, the worst-case running time when using adjacency matrices is <IMG WIDTH=43 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70999" SRC="img2255.gif" >.<P> Enumerating the edges incident on vertex <I>w</I> is a non-trivial operation when using adjacency lists. It is necessary to search every adjacency list in order to find all the edges incident on a given vertex. Therefore, the worst-case running time is <IMG WIDTH=81 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71119" SRC="img2282.gif" >.<P> This operation is performed using the enumerator obtained using the <tt>getIncidentEdges</tt> property of the <tt>Vertex</tt> interface.<P> </DL>Table <A HREF="page547.html#tblgraph2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> summarizes these running times.<P><P><A NAME="49890"> </A><P> <A NAME="tblgraph2"> </A> <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=3 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=LEFT><COL ALIGN=CENTER><COL ALIGN=CENTER><TBODY><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=2> representation scheme</TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP><P> operation </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> adjacency matrix </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> adjacency list </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>find edge (<I>v</I>,<I>w</I>) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(1) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=65 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71105" SRC="img2280.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> enumerate all edges </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=50 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline70923" SRC="img2242.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=81 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71119" SRC="img2282.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> enumerate edges emanating from <I>v</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=43 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70999" SRC="img2255.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=65 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71105" SRC="img2280.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> enumerate edges incident on <I>w</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=43 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70999" SRC="img2255.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=81 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71119" SRC="img2282.gif" > </TD></TR></TBODY><CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Comparison of graph representations.</CAPTION></TABLE></P></DIV><P><HR><A NAME="tex2html7448" HREF="page548.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7446" HREF="page545.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7442" HREF="page546.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7450" 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 + -
显示快捷键?