📄 page531.html
字号:
<HTML><HEAD><TITLE>Adjacency Lists</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="tex2html7269" HREF="page532.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7267" HREF="page528.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7263" HREF="page530.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7271" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0016113000000000000000">Adjacency Lists</A></H3><P>One technique that is often used for a sparse graph, say <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70549" SRC="img2166.gif" >,uses <IMG WIDTH=18 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70975" SRC="img2249.gif" > linked lists--one for each vertex.The linked list for vertex <IMG WIDTH=44 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline70679" SRC="img2193.gif" > containsthe elements of <IMG WIDTH=141 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70979" SRC="img2250.gif" >,the set of nodes adjacent to <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline70715" SRC="img2201.gif" >.As a result, the lists are called<em>adjacency lists</em><A NAME=49168> </A>.<P>Figure <A HREF="page531.html#figgraph5"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows the adjacency lists for the directed graph <IMG WIDTH=17 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline70643" SRC="img2182.gif" >of Figure <A HREF="page521.html#figgraph1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and the directed graph <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline70797" SRC="img2218.gif" > of Figure <A HREF="page525.html#figgraph3"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Notice that the total number of list elements used to representa directed graph is <IMG WIDTH=17 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70987" SRC="img2251.gif" >but the number of lists elements used to representan undirected graph is <IMG WIDTH=44 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70989" SRC="img2252.gif" >.Therefore, the space required for the adjacency lists is <IMG WIDTH=42 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70991" SRC="img2253.gif" >.<P><P><A NAME="49429"> </A><A NAME="figgraph5"> </A> <IMG WIDTH=575 HEIGHT=411 ALIGN=BOTTOM ALT="figure49172" SRC="img2254.gif" ><BR><STRONG>Figure:</STRONG> Adjacency lists.<BR><P><P>By definition, a sparse graph has <IMG WIDTH=82 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70933" SRC="img2244.gif" >.Hence the space required to represent a sparse graphusing adjacency lists is <IMG WIDTH=43 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70999" SRC="img2255.gif" >.Clearly this is asymptotically better than using adjacency matriceswhich require <IMG WIDTH=50 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline70923" SRC="img2242.gif" > space.<P><HR><A NAME="tex2html7269" HREF="page532.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7267" HREF="page528.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7263" HREF="page530.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7271" 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 + -