📄 page523.html
字号:
<HTML>
<HEAD>
<TITLE>Graphs and Graph Algorithms</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="tex2html8367" HREF="page524.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page524.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="tex2html8365" HREF="book.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/book.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="tex2html8359" HREF="page522.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page522.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="tex2html8369" 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="tex2html8370" 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>
<H1><A NAME="SECTION0017000000000000000000">Graphs and Graph Algorithms</A></H1>
<P>
<A NAME="chapgraphs"> </A>
<P>
A graph is simply a set of points
together with a set of lines connecting various points.
Myriad real-world application problems
can be reduced to problems on graphs.
<P>
Suppose you are planning a trip by airplane.
From a map you have determined the distances between the airports
in the various cities that you wish to visit.
The information you have gathered can be represented using a graph
as shown in Figure <A HREF="page523.html#figgraph0" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page523.html#figgraph0"><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> (a).
The points in the graph represent the cities
and the lines represent the distances between them.
Given such a graph, you can answer questions such as
``What is the shortest distance between LAX and JFK?''
or ``What is the shortest route that visits all of the cities?''
<P>
<P><A NAME="48347"> </A><A NAME="figgraph0"> </A> <IMG WIDTH=575 HEIGHT=451 ALIGN=BOTTOM ALT="figure47927" SRC="img2281.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2281.gif" ><BR>
<STRONG>Figure:</STRONG> Real-World Examples of Graphs<BR>
<P>
<P>
An electric circuit can also be viewed
as a graph as shown in Figure <A HREF="page523.html#figgraph0" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page523.html#figgraph0"><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> (b).
In this case the points in the graph
indicate where the components are connected (i.e., the wires)
and the lines represent the components themselves
(e.g, resistors and capacitors).
Given such a graph, we can answer questions such as
``What are the mesh equations that describe the circuit's behavior?''
<P>
Similarly, a logic circuit can be reduced to a graph
as shown in Figure <A HREF="page523.html#figgraph0" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page523.html#figgraph0"><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> (c).
In this case the logic gates are represented by the points
and arrows represent the signal flows from gate outputs to gate inputs.
Given such a graph, we can answer questions such as
``How long does it take for the signals to propagate from the inputs
to the outputs?''
or ``Which gates are on the critical path?''
<P>
Finally, Figure <A HREF="page523.html#figgraph0" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page523.html#figgraph0"><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> (d) illustrates that a graph can be used
to represent a <em>finite state machine</em>.
The points of the graph represent the states
and labeled arrows indicate the allowable state transitions.
Given such a graph, we can answer questions such as
``Are all the states reachable?''
or ``Can the finite state machine deadlock?''
<P>
This chapter is a brief introduction to the body
of knowledge known as <em>graph theory</em><A NAME=48355> </A>.
It covers the most common data structures for the representation of graphs
and introduces some fundamental graph algorithms.
<P>
<BR> <HR>
<UL>
<LI> <A NAME="tex2html8371" HREF="page524.html#SECTION0017100000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page524.html#SECTION0017100000000000000000">Basics</A>
<LI> <A NAME="tex2html8372" HREF="page536.html#SECTION0017200000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page536.html#SECTION0017200000000000000000">Implementing Graphs</A>
<LI> <A NAME="tex2html8373" HREF="page550.html#SECTION0017300000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page550.html#SECTION0017300000000000000000">Graph Traversals</A>
<LI> <A NAME="tex2html8374" HREF="page564.html#SECTION0017400000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page564.html#SECTION0017400000000000000000">Shortest-Path Algorithms</A>
<LI> <A NAME="tex2html8375" HREF="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page574.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/page574.html#SECTION0017500000000000000000'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page574.html#SECTION0017500000000000000000">Minimum-Cost Spanning Trees</A>
<LI> <A NAME="tex2html8376" HREF="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page582.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/page582.html#SECTION0017600000000000000000'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page582.html#SECTION0017600000000000000000">Application: Critical Path Analysis</A>
<LI> <A NAME="tex2html8377" HREF="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page584.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/page584.html#SECTION0017700000000000000000'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page584.html#SECTION0017700000000000000000">Exercises</A>
<LI> <A NAME="tex2html8378" 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#SECTION0017800000000000000000'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page585.html#SECTION0017800000000000000000">Projects</A>
</UL>
<HR><A NAME="tex2html8367" HREF="page524.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page524.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="tex2html8365" HREF="book.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/book.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="tex2html8359" HREF="page522.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page522.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="tex2html8369" 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="tex2html8370" 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 + -