首页 › 资源下载 › VC书籍 › wqeqwvrw rkjqhwrjwq › 源码查看
page549.html

来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 112 行
HTML
112 行
<HTML>
<HEAD>
<TITLE>Time Comparison</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="tex2html8697" HREF="page550.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page550.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="tex2html8695" HREF="page547.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page547.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="tex2html8691" HREF="page548.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page548.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="tex2html8699" 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="tex2html8700" 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>
<H3><A NAME="SECTION0017262000000000000000">Time Comparison</A></H3>
<P>
The following four operations are used extensively in the implementations
of 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_inline71901" SRC="img2389.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2389.gif"  >,
	since  <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71903" SRC="img2390.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2390.gif"  > is the length of the adjacency list associated
	with vertex <I>v</I>.
<P>
	This is the operation performed by the <tt>SelectEdge</tt>
	member function of the <tt>Graph</tt> class.
<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=24 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline71641" SRC="img2344.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2344.gif"  > matrix entries.
	Therefore, the worst-case running time needed to enumerate
	all the edges is  <IMG WIDTH=50 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline71729" SRC="img2358.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2358.gif"  >.
<P>
	On the other hand, to enumerate all the edges when using adjacency
	lists requires the traversal of  <IMG WIDTH=17 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71781" SRC="img2365.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2365.gif"  > lists.
	In all there are  <IMG WIDTH=16 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71793" SRC="img2367.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2367.gif"  > edges.
	Therefore the worst case running time is  <IMG WIDTH=82 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71915" SRC="img2391.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2391.gif"  >.
<P>
	This operation is performed using the iterator returned
	by the <tt>Edges</tt> member function of the <tt>Graph</tt> class.
<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=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline71921" SRC="img2392.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2392.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_inline71805" SRC="img2371.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2371.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=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline71921" SRC="img2392.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2392.gif"  > list.
	This takes  <IMG WIDTH=65 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71901" SRC="img2389.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2389.gif"  > time in the worst case.
<P>
	This operation is performed using the iterator returned
	by the <tt>EmanatingEdges</tt>
	member function of the <tt>Graph</tt> class.
<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=24 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline71935" SRC="img2393.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2393.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_inline71805" SRC="img2371.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2371.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=82 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71915" SRC="img2391.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2391.gif"  >.
<P>
	This operation is performed using the iterator returned
	by the <tt>IncidentEdges</tt> member function of the <tt>Graph</tt> class.
<P>
 </DL>
Table&nbsp;<A HREF="page549.html#tblgraph2" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page549.html#tblgraph2"><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> summarizes these running times.
<P>
<P><A NAME="50024">&#160;</A>
<P>
    <A NAME="tblgraph2">&#160;</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_inline71901" SRC="img2389.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2389.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> 
	    enumerate all edges
		</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=50 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline71729" SRC="img2358.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2358.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=82 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71915" SRC="img2391.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2391.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_inline71805" SRC="img2371.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2371.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=65 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71901" SRC="img2389.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2389.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_inline71805" SRC="img2371.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2371.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=82 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71915" SRC="img2391.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2391.gif"  > </TD></TR>
</TBODY>
<CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Comparison of Graph Representations</CAPTION></TABLE>
</P></DIV><P><HR><A NAME="tex2html8697" HREF="page550.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page550.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="tex2html8695" HREF="page547.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page547.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="tex2html8691" HREF="page548.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page548.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="tex2html8699" 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="tex2html8700" 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 &#169; 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>
page549.html - 源码说明

本页面展示了「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」中的 page549.html 源码文件，采用 HTML 编程语言编写，共 112 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。
虫虫下载站收录了大量与jkhrjqwhrwq相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。
⌨️ 快捷键说明

复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?