📄 page529.html
字号:
<HTML><HEAD><TITLE>Adjacency Matrices</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="tex2html7249" HREF="page530.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7247" HREF="page528.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7241" HREF="page528.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7251" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0016111000000000000000">Adjacency Matrices</A></H3><P>Consider a directed graph <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70549" SRC="img2166.gif" > with <I>n</I> vertices, <IMG WIDTH=136 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70855" SRC="img2230.gif" >.The simplest graph representation schemeuses an <IMG WIDTH=38 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68097" SRC="img1809.gif" > matrix <I>A</I> of zeroes and ones given by<P> <IMG WIDTH=332 HEIGHT=48 ALIGN=BOTTOM ALT="displaymath70841" SRC="img2231.gif" ><P>That is, the <IMG WIDTH=43 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline60455" SRC="img593.gif" > element of the matrix,is a one only if <IMG WIDTH=50 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline70863" SRC="img2232.gif" > is an edge in <I>G</I>.The matrix <I>A</I> is called an<em>adjacency matrix</em><A NAME=49121> </A><A NAME=49122> </A>.<P>For example, the adjacency matrix for graph <IMG WIDTH=17 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline70643" SRC="img2182.gif" > in Figure <A HREF="page521.html#figgraph1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is<P> <IMG WIDTH=323 HEIGHT=76 ALIGN=BOTTOM ALT="displaymath70842" SRC="img2233.gif" ><P>Clearly, the number of ones in the adjacency matrix is equalto the number of edges in the graph.<P>One advantage of using an adjacency matrix is that it is easy todetermine the sets of edges emanating from a given vertex.For example, consider vertex <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline70715" SRC="img2201.gif" >.Each one in the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > row corresponds to an edgethat emanates from vertex <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline70715" SRC="img2201.gif" >.Conversely, each one in the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > columncorresponds to an edge incident on vertex <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline70715" SRC="img2201.gif" >.<P>We can also use adjacency matrices to represent undirected graphs.That is, we represent an undirected graph <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70549" SRC="img2166.gif" > with <I>n</I> vertices,using an <IMG WIDTH=38 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68097" SRC="img1809.gif" > matrix <I>A</I> of zeroes and ones given by<P> <IMG WIDTH=334 HEIGHT=48 ALIGN=BOTTOM ALT="displaymath70843" SRC="img2234.gif" ><P>Since the two sets <IMG WIDTH=49 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline70889" SRC="img2235.gif" > and <IMG WIDTH=49 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline70891" SRC="img2236.gif" > are equivalent,matrix <I>A</I> is symmetric about the diagonal.That is, <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70895" SRC="img2237.gif" >.Furthermore, all of the entries on the diagonal are zero.That is, <IMG WIDTH=55 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline70897" SRC="img2238.gif" > for <IMG WIDTH=64 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68947" SRC="img1982.gif" >.<P>For example, the adjacency matrix for graph <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline70797" SRC="img2218.gif" > in Figure <A HREF="page525.html#figgraph3"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is<P> <IMG WIDTH=318 HEIGHT=76 ALIGN=BOTTOM ALT="displaymath70844" SRC="img2239.gif" ><P>In this case, there are twice as many ones in the adjacencymatrix as there are edges in the undirected graph.<P>A simple variation allows us to use an adjacency matrixto represent an edge-labeled graph.For example, given numeric edge labels,we can represent a graph (directed or undirected)using an <IMG WIDTH=38 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68097" SRC="img1809.gif" > matrix <I>A</I> in which the <IMG WIDTH=26 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68117" SRC="img1815.gif" >is the numeric label associated with edge <IMG WIDTH=45 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline70909" SRC="img2240.gif" >in the case of a directed graph,and edge <IMG WIDTH=49 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline70889" SRC="img2235.gif" >,in an undirected graph.<P>For example, the adjacency matrix for the graph <IMG WIDTH=19 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline70827" SRC="img2227.gif" > in Figure <A HREF="page527.html#figgraph4"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is<P> <IMG WIDTH=334 HEIGHT=76 ALIGN=BOTTOM ALT="displaymath70845" SRC="img2241.gif" ><P>In this case, the array entries corresponding to non-existent edgeshave all been set to <IMG WIDTH=14 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline68397" SRC="img1875.gif" >.Here <IMG WIDTH=14 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline68397" SRC="img1875.gif" > serves as a kind of <em>sentinel</em><A NAME=49143> </A>.The value to use for the sentinel depends on the application.For example, if the edges represent routes between geographic locations,then a route of length <IMG WIDTH=14 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline68397" SRC="img1875.gif" > is much like one that does not exist.<P>Since the adjacency matrix has <IMG WIDTH=25 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline70835" SRC="img2228.gif" > entries,the amount of spaced needed to represent the edges ofa graph is <IMG WIDTH=50 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline70923" SRC="img2242.gif" >,<em>regardless of the actual number of edges</em> in the graph.If the graph contains relatively few edges,e.g., if <IMG WIDTH=69 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline70925" SRC="img2243.gif" >,then most of the elements of the adjacency matrix will be zero (or <IMG WIDTH=14 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline68397" SRC="img1875.gif" >).A matrix in which most of the elements are zero (or <IMG WIDTH=14 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline68397" SRC="img1875.gif" >)is a <em>sparse matrix</em><A NAME=49146> </A><A NAME=49147> </A>.<P><HR><A NAME="tex2html7249" HREF="page530.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7247" HREF="page528.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7241" HREF="page528.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7251" 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 + -