📄 page544.html
字号:
<HTML>
<HEAD>
<TITLE>Using Adjacency Matrices</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="tex2html8641" HREF="page545.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page545.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="tex2html8639" HREF="page543.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page543.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="tex2html8633" HREF="page543.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page543.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="tex2html8643" 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="tex2html8644" 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="SECTION0017241000000000000000">Using Adjacency Matrices</A></H3>
<P>
The <tt>GraphAsMatrix</tt> class is declared in Program <A HREF="page544.html#proggraph4h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page544.html#proggraph4h"><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>.
The <tt>GraphAsMatrix</tt> class is a concrete class derived
from the base class <tt>Graph</tt> which is shown in Program <A HREF="page539.html#proggraph3h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page539.html#proggraph3h"><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>.
Since <tt>GraphAsMatrix</tt> is a concrete class,
it must provide implementations for all the member functions
declared as pure virtual functions in the base classes--the function prototypes have been elided for the sake of brevity.
<P>
<P><A NAME="50107"> </A><A NAME="proggraph4h"> </A> <IMG WIDTH=575 HEIGHT=180 ALIGN=BOTTOM ALT="program49884" SRC="img2379.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2379.gif" ><BR>
<STRONG>Program:</STRONG> <tt>GraphAsMatrix</tt> Class Definition<BR>
<P>
<P>
Each instance of the <tt>GraphAsMatrix</tt> class
represents an undirected graph, say <IMG WIDTH=72 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71355" SRC="img2282.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2282.gif" >.
The two member variables,
<tt>vertices</tt> and <tt>adjacencyMatrix</tt>,
are used to represent the sets <IMG WIDTH=10 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline71357" SRC="img2283.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2283.gif" > and <IMG WIDTH=9 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline71363" SRC="img2284.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2284.gif" >, respectively.
<P>
The set of vertices, <IMG WIDTH=10 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline71357" SRC="img2283.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2283.gif" >, is represented using a one-dimensional
array of pointers to <tt>Vertex</tt> instances.
The implementation uses the <tt>Array<T></tt> class
given in Section <A HREF="page80.html#secfdsarrays" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page80.html#secfdsarrays"><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>.
The set of edges, <IMG WIDTH=9 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline71363" SRC="img2284.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2284.gif" >, is represented using a two-dimensional
matrix of pointers to <tt>Edge</tt> instances.
The implementation uses the <tt>Array2D<T></tt> class
given in Section <A HREF="page100.html#secfdsmultid" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page100.html#secfdsmultid"><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>.
<P>
The <tt>GraphAsMatrix</tt> constructor takes a single argument
of type <tt>unsigned int</tt> that specifies
the maximum number of vertices that the graph may contain.
This quantity specifies the length of the
array of vertices and the dimensions of the adjacency matrix.
The implementation of the <tt>GraphAsMatrix</tt> class is left
as programming project for the reader (Project <A HREF="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page585.html \n\nThis file was not retrieved by Teleport Pro, because the server reports that an error occurred that prevented retrieval. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page585.html#projectgraphsmatrix'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page585.html#projectgraphsmatrix"><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>).
<P>
<HR><A NAME="tex2html8641" HREF="page545.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page545.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="tex2html8639" HREF="page543.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page543.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="tex2html8633" HREF="page543.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page543.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="tex2html8643" 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="tex2html8644" 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 © 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>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -