📄 page558.html
字号:
<HTML>
<HEAD>
<TITLE>Implementation</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="tex2html8811" HREF="page559.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page559.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="tex2html8809" HREF="page557.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page557.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="tex2html8803" HREF="page557.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page557.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="tex2html8813" 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="tex2html8814" 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="SECTION0017331000000000000000">Implementation</A></H3>
<P>
Instead of implementing an algorithm that computes a topological sort,
we have chosen to implement a traversal that visits the vertices
of a DAG in the order given by the topological sort.
The topological order traversal can be used
to implement many other graph algorithms.
Furthermore, given such a traversal,
it is easy to define a visitor that computes a topological sort.
<P>
In order to implement the algorithm described in the preceding section,
an array of integers of length <IMG WIDTH=17 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71781" SRC="img2365.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2365.gif" > is used
to record the in-degrees of the vertices.
As a result, it is not really necessary to remove
vertices or edges from the graph during the traversal.
Instead, the effect of removing a vertex
and all the edges emanating from that vertex
is simulated by decreasing the apparent in-degrees
of all the successors of the removed vertex.
<P>
In addition, we use a queue to keep track of the vertices
that have not yet been visited,
but whose in-degree is zero.
Doing so eliminates the need to search the array for zero entries.
<P>
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> defines the <tt>TopologicalOrderTraversal</tt>
routine of the <tt>Digraph</tt> class.
This routine takes as its lone argument a reference to a visitor instance.
The <tt>Visit</tt> function of the visitor
is called once for each vertex in the graph.
The order in which the vertices are visited is given by
a topological sort of those vertices.
<P>
<P><A NAME="50869"> </A><A NAME="proggraph3c"> </A> <IMG WIDTH=575 HEIGHT=678 ALIGN=BOTTOM ALT="program50808" SRC="img2415.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2415.gif" ><BR>
<STRONG>Program:</STRONG> <tt>Digraph</tt> Class <tt>TopologicalOrderTraversal</tt> Member Function Definition<BR>
<P>
<P>
The algorithm begins by computing the in-degrees of all the vertices.
An array of unsigned integers of length <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" > called <tt>inDegree</tt>
is used for this purpose.
First, all the array elements are set to zero.
Then, for each edge <IMG WIDTH=78 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72081" SRC="img2416.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2416.gif" >,
array element <IMG WIDTH=92 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72083" SRC="img2417.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2417.gif" > is increased by one (lines 3-12).
<P>
Next, a queue to hold vertices is created.
Since the vertices are owned by the graph,
the <tt>RescindOwnership</tt> member function of the queue is called.
That way, the queue will not attempt to delete any contained vertices
when its destructor is called.
After the queue has been initialized,
all vertices with in-degree zero are enqueued (lines 14-18).
<P>
The main loop of the <tt>TopologicalOrderTraversal</tt> routine
comprises lines 19-33.
This loop continues as long as the queue is not empty
and the visitor is not finished.
In each iteration of the main loop exactly one vertex is dequeued
and visited (lines 21-23).
<P>
Once a vertex has been visited,
the effect of removing that vertex from the graph is simulated
by decreasing by one the in-degrees of all the successors of that vertex.
When the in-degree of a vertex becomes zero,
that vertex is enqueued (lines 24-30).
<P>
<HR><A NAME="tex2html8811" HREF="page559.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page559.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="tex2html8809" HREF="page557.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page557.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="tex2html8803" HREF="page557.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page557.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="tex2html8813" 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="tex2html8814" 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 + -