📄 page519.html
字号:
<HTML><HEAD><TITLE>Graphs and Graph Algorithms</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="tex2html7124" HREF="page520.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7122" HREF="book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7116" HREF="page518.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7126" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0016000000000000000000">Graphs and Graph Algorithms</A></H1><P><A NAME="chapgraphs"> </A><P>A graph is simply a set of pointstogether with a set of lines connecting various points.Myriad real-world application problemscan 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 airportsin the various cities that you wish to visit.The information you have gathered can be represented using a graphas shown in Figure <A HREF="page519.html#figgraph0"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (a).The points in the graph represent the citiesand 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="48114"> </A><A NAME="figgraph0"> </A> <IMG WIDTH=575 HEIGHT=451 ALIGN=BOTTOM ALT="figure47694" SRC="img2165.gif" ><BR><STRONG>Figure:</STRONG> Real-world examples of graphs.<BR><P><P>An electric circuit can also be viewedas a graph as shown in Figure <A HREF="page519.html#figgraph0"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (b).In this case the points in the graphindicate 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 graphas shown in Figure <A HREF="page519.html#figgraph0"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (c).In this case the logic gates are represented by the pointsand 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 inputsto the outputs?''or ``Which gates are on the critical path?''<P>Finally, Figure <A HREF="page519.html#figgraph0"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (d) illustrates that a graph can be usedto represent a <em>finite state machine</em>.The points of the graph represent the statesand 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 bodyof knowledge known as <em>graph theory</em><A NAME=48122> </A>.It covers the most common data structures for the representation of graphsand introduces some fundamental graph algorithms.<P><BR> <HR><UL> <LI> <A NAME="tex2html7127" HREF="page520.html#SECTION0016100000000000000000">Basics</A><LI> <A NAME="tex2html7128" HREF="page532.html#SECTION0016200000000000000000">Implementing Graphs</A><LI> <A NAME="tex2html7129" HREF="page548.html#SECTION0016300000000000000000">Graph Traversals</A><LI> <A NAME="tex2html7130" HREF="page563.html#SECTION0016400000000000000000">Shortest-Path Algorithms</A><LI> <A NAME="tex2html7131" HREF="page573.html#SECTION0016500000000000000000">Minimum-Cost Spanning Trees</A><LI> <A NAME="tex2html7132" HREF="page581.html#SECTION0016600000000000000000">Application: Critical Path Analysis</A><LI> <A NAME="tex2html7133" HREF="page583.html#SECTION0016700000000000000000">Exercises</A><LI> <A NAME="tex2html7134" HREF="page584.html#SECTION0016800000000000000000">Projects</A></UL><HR><A NAME="tex2html7124" HREF="page520.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7122" HREF="book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7116" HREF="page518.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7126" 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 + -