Chapter 9. Trees
Click here to access a summary of all the Maple code used in this section.
This chapter is devoted to computation aspects of the study of trees. Trees are a specific type of graph, that is connected simple graphs that have no simple circuits.
The Maple code in this chapter assumes that you are using an upgraded version of Maple's networks package. These enhancements primarily affect the display of trees. In particular, the draw command has been updated to understand how to draw rooted trees. To test that you are using correct version, load the networks package and run the command version, as in
with(networks): version();
If this command does not produce a description of the version, then you are using the wrong version. An appropriate version can be found at the ftp site at http://www.mhhe.com/math/advmath/rosen/r5/instructor/maple.html along with installation instructions.
First, we will discuss how to represent, display, and work with trees using Maple. Specifically, we will describe how to represent and construct trees and derive basic characteristics about trees in Maple. We will show how to use Maple to display trees. We will show how to solve a variety of problems, where trees play an important role using Maple, such as in searching and in constructing prefix codes using a specific implementation of the Huffman coding algorithm. We will describe how to use Maple to carry out different methods of traversing trees, where a traversal is a visiting of vertices in some predefined order. Then we will discuss how these traversals relate to the topic of sorting. We continue by showing how to use Maple to create spanning trees of graphs. Then, we will show to use Maple to solve a variety of problems via backtracking. Finally, we will show how to find minimum weight spanning trees of weighted graphs using Maple.
1. Introduction to Trees
Click here to access a summary of all the Maple code used in this section.
To begin, we will demonstrate how to construct trees in Maple. Given an unrooted tree, we can construct this tree in Maple just as we would any graph. We will also provide a procedure that uses some builtin capabilities of Maple that determines whether a specific graph is a tree.
Before delving into the implementation, there are two important points that must be stressed. First, we note that Maple differs from the terminology of the text in the sense that Maple refers to simple cycles when the text refers to simple circuits. The second noteworthy point is that an unrooted tree is a simple graph that has no simple cycles. A rooted tree is exactly the same structurally as an unrooted tree, with the additional property that there is a specific vertex, called the root, which is viewed as the starting point in a tree. In terms of Maple implementation, we represent unrooted trees as graphs, and we create rooted trees from unrooted trees by using Maple commands such as spantree, which will be covered later, by specifying a desired root of an unrooted tree.
One other important type of tree is an ordered tree, which is a rooted tree where the children of a vertex of ordered in some manner, such as children if there are m children of a given vertex. We will make use of vertex weights to determine the order of children of a specific vertex. This type of tree will arise later, but it is important to distinguish between unrooted trees, rooted and unordered trees, and rooted and ordered trees.
As a first example, we will discuss unrooted trees. We create a tree in exactly the same fashion as we created a graph, using the networks package of Maple. As our first example, we will create a simple tree on 4 vertices.
with(networks): new(T1): addvertex(a,b,c,d,f,g,T1): addedge(a,b,a,c,a,d,b,f,b,g, T1): draw(Tree(a),T1);
Suppose that we were given a graph and were asked to determine whether or not it was a tree. By the definition of trees, we need to verify the following 3 properties:

The graph is connected.

The graph is simple.

The graph has no cycles.
Using Maple, these properties are easily checked. In particular, we can determine whether a graph is connected in Maple by using the components command, which returns a collection of sets of vertices, where each set in this collection contains the vertices from a connected component of the graph. We can determine whether a graph is simple by using the Maple command gsimp, that returns the underlying simple tree of a multigraph, and then comparing the number of edges of the underlying simple tree to the original graph. This leads to the procedure IsSimple.
IsSimple := proc(G::graph) local H; H := networks[duplicate](G); if nops(edges(gsimp(H))) = nops(edges(G)) then true else false fi; end:
Note that we should not simplify G itself as such a simplification is an irreversible process.
To test for connectivity we provide the procedure IsConnected
IsConnected := proc(G::graph) evalb(nops(components(G)) = 1) end:
We can determine whether a graph has no cycles by using the cyclebase command of Maple that returns a set of cycles, or simple circuits, that form a basis of all cycles (simple circuits) in the given graph; if the cyclebase has no cycles, the graph has no cycles. This, together with the two previous tests can be used to provide a test if a graph is a tree.
IsTree:=proc(G::graph) if not (IsConnected(G) and IsSimple(G)) then RETURN(false); fi; if cyclebase(G) = {} then RETURN(true); else RETURN(false); fi; end:
If you prefer, you can replace the cycle base test in this procedure by one which checks to see if the number of edges is one less than the number of vertices.
We are now ready to use the IsTree procedure to determine whether some particular graphs are trees;
IsTree(T1); IsTree(complete(3));
1.1. Rooted Trees
Click here to access a summary of all the Maple code used in this section.
Up to this point we have dealt with only unrooted trees. We can use the Maplespantree command to change an unrooted tree into a rooted tree. It accomplishes this by updating the sets of ancestors and daughters (descendents) for each vertex, to reflect the structure of the spanning tree.
To use the spantree command, we select a vertex and form a spanning tree with this vertex as the root, directing all edges in the tree towards the root. (We will study spanning trees later in this chapter. Generally, the spantree command takes an undirected connected graph G and a vertex v of the graph and constructs a spanning tree of G using v as the root, directing all edges towards v.) For example, we can make the tree T1 into a rooted tree, taking a as its root using the command
T2:=spantree(T1, a):
We can easily examine relationships between the vertices of a tree using builtin Maple commands. Among the commands that are useful for this are the daughter, ancestor, neighbors and departures commands. The daughter command finds the children of a vertex in a rooted tree, and the ancestor command of Maple finds the parent vertex of a vertex in a rooted tree. The neighbors and departures act in a similar manner, determining the children of a vertex in the rooted tree.
To illustrate the usage of some of these commands in Maple, we can examine relationships of trees such as parents, children, ancestors and descendants of specific vertices. For instance, we can find the children of the vertex a in the tree T2, using the command:
daughter(a, T2);
To find the parent of d in the tree T2, we use the command:
ancestor(d, T2);
We now present a procedure that finds all the descendants, ancestors, and siblings of a particular vertex in a rooted tree. This procedure, called Family, can be described using the following pseudocode:

To find all ancestors, we use the ancestor command of Maple until there are no more ancestors (i.e. when we reach the root vertex).

To find all descendants, we use the daughter command repeatedly until there are no more descendants (i.e. when all leaves from a vertex have been reached).

To find all siblings of a vertex v, we first find the ancestor of v, called w; the siblings of v are the descendants of w other than v.
An implementation of this procedure is as follows:
Family := proc(v::name,G::graph) local Temp, Ancestors, Descendants, Siblings; Ancestors := ancestor(v,G); Temp := ancestor(v,G); while not (Temp = {}) do Ancestors := Ancestors union Temp; Temp := ancestor(Ancestors,G); od; Descendants := daughter(v,G); Temp := daughter(v,G); while not (Temp = {}) do Descendants := Descendants union Temp; Temp := daughter(Descendants,G); od; Siblings := daughter(ancestor(v, G), G) minus v; [Ancestors,Siblings,Descendants]; end:
We will now build a larger tree, called T3 which is the tree shown on Page 5433 of the text, and then we will execute the newly created procedure on one of its vertices.
new(T3): addvertex(A,B,C,D,E,F,G,H,I,J,K,L,M,N,T3): addedge( [A,B],[A,J],[A,K],[B,C],[B,E],[B,F], [C,D],[F,G],[F,I],[G,H],[K,L],[L,M],[L,N], T3): draw(Tree(A),T3);
The descendants of the vertex B are obtained by the commands
Bfamily := Family(B,T3); Bfamily[3];
Next, we determine the set of internal vertices and leaves of a rooted tree. Recall that an v is an internal vertex of a rooted tree if v has children, and that v is a leaf vertex of a rooted tree if v has no children. In other words, in any nontrivial rooted tree (i.e. a rooted tree that is more than a single root vertex), the leaves are those with vertex degree 1, and the internal vertices are vertices with vertex degree greater than 1.
Knowing this, we can use the Maplevdegree command to determine the set of leaves and the set of internal vertices of a given rooted tree.
Leaves:=proc(T::graph, root::name) select( proc(x,T) evalb( vdegree(x,T) < 2 ) end, vertices(T) minus root , T ); end: Internal:=proc(T::graph, root::name) select( proc(x,T) evalb( vdegree(x,T) > 1 ) end, vertices(T) minus root , T ); end: Leaves(T2, a); Internal(T2,a);
We will now discuss how to find the largest number of children of an internal vertex of a rooted tree. Recall that if m is this number, the tree is called an mary tree. We will also describe how to determine if an mary tree is balanced. Recall that a tree is balanced if all the leaves are at level h or h1 if a tree has a total of h levels, where the level of a vertex is the length of the unique path from the root to that vertex.
To use Maple for determining whether a tree is an mary tree, we can simply look at the degree sequence of the vertices, taking into account that for all vertices except the root, the degree of that vertex is one more than the number of descendants. This can be accomplished by using the vdegree command in Maple. To determine whether a tree is balanced, we can use the internal storage structure of a tree in Maple. We will use the fact that Maple stores the level of a vertex in a tree as the vertex weight for that vertex. For instance, if v is a vertex that is at level 3 in a tree, then we can extract this information by using the vweight command on the vertex v.
This technique is formalized by the following Maple procedure:
ArityBalanced:=proc(G::graph, Root::name) local Leaf_Depth, V, Max_Children, is_balanced,i; V:=vertices(G); Leaf_Depth:={}; is_balanced:=false; for v in V do if (not (v = Root)) and (vdegree(v,G)=1) then Leaf_Depth:=Leaf_Depth union vweight(v, G); fi; od; if nops(Leaf_Depth) > 2 then printf(`The tree is not balanced`); elif nops(Leaf_Depth) = 1 then printf(`The tree is balanced`); is_balanced:=true; elif nops(Leaf_Depth) = 2 and abs(Leaf_Depth[1]  Leaf_Depth[2]) > 1 then printf(`The tree is not balanced`); else printf(`The tree is balanced %a`, Leaf_Depth ); is_balanced:=true; fi; Max_Children:=maxdegree(G)1; if vdegree(Root, G) > Max_Children then Max_Children:=vdegree(Root, G); fi; printf(`The arity of the tree is %d`, Max_Children); [Max_Children, is_balanced]; end:
ArityBalanced(T3, A):
We will now use the ArityBalanced procedure to verify the formulae on page 541 of the text for full mary trees. That is, we will construct a procedure to compute the number of internal vertices and leaves of a given mary tree, and compare these quantities as outlined in Theorem 3 and Theorem 4 on page 541 of the text. The procedure called TheoremVerify will use
TheoremVerify:=proc(G::graph, Root::name) local internal, m, leaves, n, i, V, is_full_tree; V:=vertices(G); n:=nops(V); i:=0; internal:=0; leaves:=0; is_full_tree:=true;
Use the ArityBalanced procedure to determine arity
m:=ArityBalanced(G, Root)[1]; while is_full_tree and i<n do i:=i+1;
If there are no children of the vertex, it is a leaf
if nops(daughter(V[i], G)) = 0 then leaves:=leaves+1;
If the number of children is not m, then it is not a full tree
elif not (nops(daughter(V[i],G)) = m) then printf(`The tree is not a full tree`); is_full_tree:=false;
The current vertex is an internal vertex
else internal:=internal+1; fi; od; if is_full_tree then printf(`Vertices count is %d`, n); printf(`Computed count (m*i+1) is %d`, m*internal + 1); printf(`Leaf count is %d`, leaves); printf(`Computed count ((m1)*i + 1) is %d`, (m1)*internal+1); fi; NULL; end:
We will use the TheoremVerify procedure to verify Theorems 3 and 4 from the text on a full 3ary tree.
new(Full1): addvertex(A,2,3,4,5,6,7,8,9,10, Full1): addedge(A,2, A,3, A,4, 2,5, 2, 6, 2,7, 4,8, 4,9, 4,10, Full1):
TheoremVerify(Full1, A);
2. Application of Trees
Click here to access a summary of all the Maple code used in this section.
This section is concerned with the use of trees in binary search trees. Specifically, we address the use of trees in binary search algorithms as well as the use of trees in Huffman codes. The reason that we wish to use binary trees is that we can use the binary structure of the tree to make binary decisions (i.e. true/false) regarding insertion or search paths.
A tree is called a binary tree if all vertices in the tree have at most two children. In this chapter, we will be using ordered binary trees. The ordering of the vertices is simply a labeling of the children of a vertex as either the left child or the right child, where the left child is regarded as the child that should be visited first, and the right child is the child that should be visited second.
2.1. Binary Insertion
Click here to access a summary of all the Maple code used in this section.
A key benefit of ordered binary trees is that the search time required to find a specific element of the tree is logarithmic in the number of vertices of the tree. The major drawback is that the initial insertion of a vertex is much more expensive. We discuss these in greater detail as we go through the actual implementation of a binary insertion algorithm.
We require vertex labels. In Maple we can use the name of the vertex as a label as it can be either an integer or a character string.
A typical vertex in the tree has two descendents (daughters). We must be able to specify which of these two vertices is the left descendent, and which is the right. We can indicate this by using the weight of the vertex. In Maple, each vertex has a default weight of 0 as shown by the simple example
new(g): addvertex(1,2,g): vweight(1,g);
We can use the weight of the vertex to specify a left to right ordering. An even simpler solution is simply to agree that the weight of the vertex is its name and to impose an ordering on those names.
To compare two vertex names, we can use a procedure such as
IsLessThan := proc(a,b) local t; if type( [a,b], [string,string]) then t := sort( [a,b] , lexorder ); else t := sort([a,b]); fi; if a = t[1] then true else false fi; end:
Using this comparison allows us to generally ignore what type of label is being used.
IsLessThan(1,2); IsLessThan(b,a); IsLessThan(1,b);
It also makes it easier to change the comparison criteria at some later point without recoding the entire algorithm.
We will also need to be able to find the root of the tree. The following procedure calculates such a root and forces the tree to remember its root so that the computation does not need to be repeated.
FindRoot := proc(T::GRAPH) local v, V; V := vertices(T); if not assigned( T(Root) ) then for v in V do if indegree(v,T) = 0 then T(Root) := v; # remember the root fi; od; if not assigned( T(Root) ) then ERROR(`no root`) fi; fi; T(Root); end:
The procedure for constructing an ordered binary tree by insertion is as follows. For simplicity, we use the vertex name as its value when doing comparisons.

Given a vertex v to insert into tree T, we need to locate the correct place in the the tree T to insert v

If the tree T is empty, insert v as the root

Otherwise, make the root of the tree the current vertex cur_vertex and compare v with cur_vertex. If cur_vertex you are done.

If cur_vertex then search the left child, otherwise, search the right child. This is accomplished by changing cur_vertex to be either the left or the right child and comparing the new cur_vertex with v.

Eventually, we will not be able to go search in the direction the comparison says we should go. At this point, insert v as the missing child of cur_vertex.
A detailed implementation of the algorithm is as follows.
Binsertion := proc(T::graph, x::string,integer) local cur_vertex, V, i, Kids, Left, Right; V := vertices(T); if nops(V) = 0 then addvertex(x, T); T(Root) := x ; # remember the root for later RETURN( x ); fi;
We have a rooted tree ...
cur_vertex := FindRoot(T); while x <> cur_vertex do
The relative orderings of the descendants and x and cur_vertex determine if x can be added as a leaf.
Kids := daughter(cur_vertex,T); Kids := sort( convert(Kids,list) , IsLessThan ); Candidates := sort( [ x, cur_vertex, op(Kids)], IsLessThan );
Begin with the easy cases.
if nops(Candidates) = 2 then
no children so just add in new vertex.
if IsLessThan(x,cur_vertex) then addvertex(x,weight=`Lft`,T); else addvertex(x,weight=`Rht`,T); fi; addedge( [cur_vertex,x] , T); cur_vertex := x; break; elif nops(Candidates)=4 then
two descendents so no insertion at this level ...
if IsLessThan(x,cur_vertex) then cur_vertex := Kids[1]; else cur_vertex := Kids[2]; fi; next; elif nops(Candidates) = 3 then
not this level if pattern is [x,L,cur_vertex] or [L,x,cur_vertex] [cur_vertex,L,x] or [cur_vertex,x,L]
if Candidates[1] = cur_vertex or Candidates[3] = cur_vertex then cur_vertex := Kids[1]; next; fi;
For all remaining cases add in x as a new vertex
if IsLessThan(x,cur_vertex) then addvertex(x,weight=`Lft`,T); else addvertex(x,weight=`Rht`,T); fi;
Yes! This level.
addedge( [cur_vertex,x] , T); cur_vertex := x; break; fi; od; RETURN( cur_vertex ); end:
The addvertex procedure is used here in a manner which updates the weights of each vertex as it is created. This is to indicate if the vertex is a left or right descendent. While we do not use these weights, they could be used as an alternative measure for sorting the descendents of any particular vertex.
Instead, for sorting we use the names of the vertices to indicate the relative ordering of vertices. The fact that any two vertices (not just descendants of the same vertex) can be compared allows us to combine the new vertex, the descendents, and the current vertex all into one sorted list which is then inspected to determine which of the many special cases is relevant during the insertion of a new vertex. Whatever method of comparing vertices is used, it is important that the comparison procedure be passed on to the sort routine as an extra argument.
To validate this procedure, examine how the following list of integers is added:
Num_List:=[4,6,2,8,5,3,7,1]: new(Tree_Num): for i from 1 to 8 do Binsertion(Tree_Num, Num_List[i]); od;
To see the resulting tree and its structure, use the Mapledraw command.
draw(Tree(4), Tree_Num);
The result is clearly a binary search tree.
Binary trees exist to be searched. The following procedure BiSearch does so. Print statements have been added to illustrate the path that the algorithm uses while searching the tree.
BiSearch := proc(T::graph, v) local i, Kids, cur_vertex; cur_vertex := FindRoot(T); while v <> cur_vertex do print(cur_vertex);
check the easy cases
if v = cur_vertex then RETURN(true); fi; Kids := daughter(cur_vertex,T); if Kids = {} then RETURN( false) fi;
descendants so start looking ...
Kids := sort( convert(Kids,list) ); Candidates := sort( [v , cur_vertex, op(Kids)], IsLessThan); if nops(Candidates) = 4 then # both descendents if IsLessThan(cur_vertex,v) then cur_vertex := Kids[2]; else cur_vertex := Kids[1]; fi; next; # back to top of loop elif nops(Candidates) = 3 then
not present unless cur_vertex is the first or the last in the list
if Candidates[1] <> cur_vertex and Candidates[3] <> cur_vertex then RETURN( false ); fi; cur_vertex := Kids[1]; next; fi; od; RETURN(true); end:
To test this procedure, we try searching for two elements, one of which is in the tree and one of which is not. Tree_Num;
BiSearch(Tree_Num,8); BiSearch(Tree_Num,12);
2.2. Huffman Coding
Click here to access a summary of all the Maple code used in this section.
Huffman coding is a method for constructing an efficient prefix code for a set of characters. It is based on a greedy algorithm, where at each step the vertices with the least weight are examined. Huffman coding can be shown to produce optimal prefix codes. The following pseudocode describes an algorithm for Huffman coding. (For a fuller discussion of Huffman coding, see Cormen, Leiserson, and Rivest, Introduction to Algorithms, MIT Press, 1989.)

Begin by creating an ordered list of the elements to be coded, where the ordering is with respect to the frequency of occurrence of these elements. Consider each element of the list as a vertex with weight equal to its frequency of occurrence.

Remove the first two elements, x and y, from this list

Assign x as the left child and y as the right child of a new vertex z in our tree

Assign the weight of z to be the sum of the weights of x and y

Insert z into the correct position of our list and repeat step (2).

Upon completion, our list contains only one element, which is a rooted binary tree.
Once again, a special comparison routine is required. Code elements are represented by lists such as [a,15] and [b,10]. The following procedure HuffCompare compares two such elements.
HuffCompare :=proc(a::list,b::list) if a[2] <= b[2] then true else false fi; end:
For example, we find that .
HuffCompare([b,10],[a,15]);
Using this method of comparison, lists of code elements can be sorted into ascending order.
sort( [[a,5],[b,10],[c,8],[d,11]], HuffCompare);
The full Huffman Encoding algorithm is implemented as follows:
Huffman:=proc(L::listlist) local i, j, k, n, Q, T, x, y, z, Temp; new(T); Q := sort( L , HuffCompare ); i := 1; while(nops(Q)>1) do i := i+1;
get the first two code elements
x:=Q[1]; Q:=subsop(1=NULL, Q); y:=Q[1]; Q:=subsop(1=NULL, Q);
build the new vertex and its location
z := [ i , x[2]+y[2]]; for j to nops(Q) while HuffCompare( z, Q[j]) do j := j+1; od; j := j1;
add the vertices and edges to the tree
Q := [seq(Q[k],k=1..j),z,seq(Q[k],k=j+1..nops(Q))]; addvertex([x[1],y[1],z[1]],weights=[x[2],y[2],z[2]],T); addedge([z[1],x[1]],[z[1],y[1]],T); od; RETURN( eval(T) ); end:
The type listlist denotes a list of lists. The final eval is included to ensure that the result returned by the procedure is the actual tree and not just its name.
Try this newly created procedure on the following list of English characters paired with a relative frequency of occurrence;
Huf:=Huffman([[f,15],[b,9],[d,22],[c,13],[a,16],[e,45]]):
To see the result we again use the Mapledraw command;
rt := FindRoot(Huf); draw(Tree(rt), Huf);
3. Tree Traversal
Click here to access a summary of all the Maple code used in this section.
In this section we show how to use Maple to carry out tree traversals. Recall that a tree traversal algorithm is a procedure for systematically visiting every vertex of an ordered rooted tree. In particular, we will provide procedures for three important tree traversal algorithms: preorder traversal, inorder traversal, and postorder traversal. We will then show how to use these traversal methods to produce the prefix, infix, and postfix notations for arithmetic expressions.
These tree traversals rely on the construction of ordered rooted trees. We shall use vertex weights to represent the order of children, as was done in earlier sections.
We create an ordered tree, based on the tree of Figure 3 on page 5566 of the text, in order to see the behavior of the various tree traversals. Then, the graph becomes
d := 'd':
new(Trav): addvertex( [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p], weights=[0,1,2,3,1,2,1,2,3,1,2,1,2,1,2,3], Trav): addedge( [[a,b],[a,c],[a,d],[b,e],[b,f],[d,g],[d,h], [d,i],[e,j],[e,k],[g,l],[g,m],[k,n],[k,o],[k,p]], Trav): draw(Tree(a),Trav);
The weights added to the vertices here represent the number of that vertex in terms of its parent. For example, d is the 3rd child of a. As in the previous section, such weights could be used for sorting, though in fact the underlying ordering is simply alphabetic on the names of the vertices.
We first implement the the preorder traversal algorithm. This visits the root and then each subtree left to right in a preorder traversal manner. In pseudocode form, the algorithm is;

Visit the root of T. Set current vertex to be the root.

Consider the children of the current vertex as roots of trees , taken in left to right order. Repeat step (1) on each of these subtrees in order.
As can be seen from step (2) of the above pseudocode, this algorithm is recursive. We provide the following implementation in Maple:
Preorder:=proc(G::graph, r) local Dep, v, T;
Visit the root
printf(`%a `, r);
Consider children of the root
Dep:= departures(r, G);
Form the correct order of children
Dep:= sort( convert(Dep,list) , IsLessThan );
Preorder traverse these subtrees in order
for v in Dep do Preorder(G, v); od; printf(``, r); end:
The order in which we traverse the descendents is determined by the boolean procedure IsLessThan (from in the previous section). To traverse the descendants in a different order, use a different comparison routine.
We can examine the execution of this procedure on the earlier created tree Trav, rooted at vertex A.
Preorder(Trav, a);
We implement inorder traversal, in a similar manner. We simply alter the sequence in which the vertices are visited. Specifically, we look at leftmost subtree vertices, followed by the root, followed by the rightmost subtree vertices. In pseudocode this is:

If the tree T has only one vertex, r then visit r

Else, the tree T has more than one vertex. Call the leftmost subtree (rooted at the leftmost child) . Inorder traverse , then visit the root r of T.

Inorder traverse the rooted subtrees .
A Maple implementation is as follows:
Inorder:=proc(G::graph, r) local v, Dep, T;
If we have reached a leaf vertex, print it
if outdegree(r, G) = 0 then print(r);
We are at an internal vertex
else Dep:=departures(r, G);
Determine order of children and traverse the subtree based at the leftmost child.
Dep := sort( convert( Dep , list ), IsLessThan ); Inorder(G, Dep[1]);
Visit the root
print(r);
Inorder traverse the remaining subtrees
for v in Dep[2..nops(Dep)] do Inorder(G, v); od; fi; NULL; end:
We have added a NULL as the last statement so that nothing is returned.
Once again, to traverse the children in a different order, use a different comparison routine to sort the descendants. Test this newly created procedure by executing it on the tree Trav.
Inorder(Trav, a);
The final traversal that we shall implement in the postorder traversal. Postorder traversal is similar to the preorder traversal, except that we visit the root after we visit each subtree. In pseudocode this is:

Consider the children of the root as subtrees , taken in left to right order.

Postorder traverse , then , up to .

Print the root of the current tree.
A Maple implementation of this procedure is as follows:
Postorder:=proc(G::graph, r::name) local v,i, Dep, T;
Consider children of the root
Dep:=departures(r, G);
Form the correct order of children
Dep:= sort( convert(Dep,list) , IsLessThan) ;
Postorder traverse these subtrees in order
for v in Dep do Postorder(G, v); od;
Visit the root
printf(` %c`, r); end:
We also test this procedure on the tree Trav with root A.
Postorder(Trav, a);
3.1. Infix, Prefix and Postfix Notation
Click here to access a summary of all the Maple code used in this section.
We will now discuss how to use Maple to work with the infix, prefix, and postfix forms of arithmetic expressions. These forms are discussed in Section 8.33 of the text. Specifically, we will show how to create a binary tree representation of an infix expression, how to use postorder and preorder traversals to create postfix and prefix forms of the expression, respectively, and how to evaluate these expressions from their postfix and prefix forms.
To begin this section, we construct a Maple procedure that takes a infix arithmetic expression and converts it into a binary tree representation. This binary tree representation can then be traversed using the traversals of the previous sections to form various arithmetic representation formats. As an example, we can construct a binary tree representation of an infix expression, such as , then execute a preorder traversal to form a prefix representation of this arithmetic expression.
In the Maple procedure that we will implement, we will consider a modified version of infix notation, to avoid complicated string manipulation that detract from the underlying problem.
Specifically, we will use lists braces instead of the normal parenthesis () of infix notation.
Additionally, we will define our operators in terms their string representations: + for addition,  for subtraction and so on.
In this way, Maple's list handling facilities are immediately available. Thus, we represent expressions such as as where + is a string.
Maple procedures can be used to help us to construct such lists. For example,
`&Plus` := proc(a,b) [a,Unique(`+`),b] end:
allows us to write and use
x &Plus y;
Maple handles procedure names of the form ... as infix operators. The procedure Unique has is defined especially for the routines used in this book and is part of the the support library for this book that is available via ftp.
The result is a list including a specially encoded version of the string + which does not collide with prior uses of + as a name. (Every vertex of the expression tree must have a different name, even if they look the same.)
Similarly we use
`&Times` := proc(a,b) [a,Unique(`*`),b] end: `&Pow` := proc(a,b) [a,Unique(`^`),b] end: `&Div` := proc(a,b) [a,Unique(`/`),b] end: `&Minus` := proc(a,b) [a,Unique(``),b] end:
so that we can write and use
x &Times y, x &Pow y;
These can be used to write the arithmetic expression as
Expr1:= (((x &Plus y) &Pow 2) &Plus ((z &Minus 4) &Div 3 ));
The result is a nested list of lists, each list representing a binary operation.
Now we are ready to construct a binary tree representing such an expression. The required algorithm in pseudocode is:

If there is a single algebraic expression (such as a name or a number) the tree consists of a single vertex.

Otherwise, the list consists of a left operand, an operator and a right operand. Use the algorithm to build a binary tree for the left operand .

Repeat step (2) on the right operand.

Combine the results of steps (2) and (3) to form the binary tree.
Our implementation is as follows:
InFixToTree:=proc(L::list,algebraic) local r1,r3, T1, T3,LocL;
If we have no sublists in our expression, return the vertices and edge lists as shown
if type(L,algebraic) then new(T1); LocL := Unique(L); addvertex(LocL,T1); T1(Root) := LocL; RETURN( eval(T1) ); fi;
L is now a list such as [a , + , b]
T1 := InFixToTree(L[1]); r1 := T1(Root); T3 := InFixToTree(L[3]); r3 := T3(Root);
construct the new tree
addvertex(vertices(T3),T1); addedge( ends(T3), T1 ); addvertex( L[2] , T1 ): addedge( [L[2],r1], [L[2],r3] , T1 ); T1(Root) := L[2]; RETURN( eval(T1) ); end:
The root of the tree is handled in a special way. Recomputing the root of the tree is awkward and expensive so we simply ask each tree to remember its own root. This is accomplished by assignment statements such as T(Root) := LocL;.
The procedure Unique is used once again to ensure each instance vertex name is unique, even if it looks the same as another. In all other aspects, the implementation is almost exactly as outlined in the pseudocode.
To test this procedure, use it to build an expression tree for the earlier expressionExpr1.
Expr1; TreeExpr1:=InFixToTree(Expr1):
To see this, draw it as a tree.
r := TreeExpr1(Root); draw(Tree(r),TreeExpr1);
Suppose we are given a binary tree representation of an arithmetic expression. We can use the earlier created algorithms to express these trees as either postfix or prefix expressions by executing the postorder or preorder traversals, respectively. Since this is straightforward, it is left up to the reader to explore this technique.
As a final example in this section, we demonstrate how to evaluate a given postfix expression. For simplicity, we have represented the the basic operations by the first letters of the words add, subtract, multiply, divide, and exponentiate. The reader is left to explore how to implement a procedure that will evaluate a prefix expression, since the technique is a simple modification of the argument that will be used in the postfix case.
Post1:=[7,2,3,M,S,4,E,9,3,D,A]; Postfix:=proc(T::list) local i, L; L:=T; while nops(L)>1 do i:=1; while not member(L[i], 'A','S','D','M','E') do i:=i+1; od; if L[i]='A' then L[i]:= L[i2]+L[i1]; elif L[i]='M' then L[i]:= L[i2]*L[i1]; elif L[i]='S' then L[i]:= L[i2]L[i1]; elif L[i]='D' then L[i]:= L[i2]/L[i1]; elif L[i]='E' then L[i]:= L[i2]^L[i1]; fi; L := [op(L[1..i3]),op(L[i..nops(L)])]; od; L; end: Postfix(Post1);
Note that in release 4, we are permitted to assign directly to list elements.
4. Trees and Sorting
Click here to access a summary of all the Maple code used in this section.
This section explains how to use Maple to carry out and analyze sorting algorithms. Trees are often used to model sorting algorithms, especially when the complexity of these algorithms is being studied. In particular, this section focuses on two of the many different sorting algorithms will be studied, the bubble sort and merge sort.
4.1. Bubble Sort
Click here to access a summary of all the Maple code used in this section.
To begin, we will examine an implementation of bubble sort. The reason why bubble sort has been given the title of "bubble" is that the smallest of the list "bubble" towards the front of the list, moving one step closer to their position after each iteration. The pseudocode, which is outlined on page 575 of the text, is as follows;

Receive as input a list, L, of n elements

Loop on index i from 1 to n1

Loop on index j from 1 to ni

If the element at position j+1 in the list L is smaller than the element at position j of L, swap these two elements
At the end of each j loop, we placed the largest i elements at the end of L.
The following procedure, called BubbleSort, is an implementation of this pseudocode.
BubbleSort:=proc(L::list) local i, j, temp, T; T:= array(L); for i from 1 to nops(L)1 do for j from 1 to nops(L)i do if T[j] > T[j+1] then temp:=T[j]; T[j] := T[j+1]; T[j+1] := temp; fi; od; od; convert(T,list); end:
Note that before starting to move elements around, we converted the list L to an array. This is because we can change each element of an array in one operation whereas to change any part of a list, we must recopy the entire list  a process involving n operations. When we are finished moving elements around we turn the array back into a list.
We can examine the execution of this procedure on an unsorted list. Note that if the list has five elements, a total of loop steps are used by the bubble sort algorithm to order these elements.
BubbleSort([3,2,4,1,5]);
4.2. Merge Sort
Click here to access a summary of all the Maple code used in this section.
We now will implement the merge sort in Maple. We will also use Maple to study the complexity of this algorithm. The merge sort algorithm can be implemented as a recursive procedure. The rough outline of the task of merge sorting a list is to split the list into two list of equal, or almost equal, size, sorting each sublist using the merge sort algorithm, and then merge the resulting lists. This can be described in pseudocode as follows:

Given a list of elements, if the list length is 1, return this list

If the list has more than two elements, Merge sort these two lists and return the merged list of the two (as the pseudocode on page 577 of the text outlines).
First we provide a procedure, Merge, that takes two sorted lists and merges them into a single sorted list, consisting of the elements in the two lists. Here is the Maple code for the Merge procedure:
Merge := proc(L1::list, L2::list) local L, i,j,k,m,n; L:=[]; i := 1; j := 1; k := 1; m := nops(L1); n := nops(L2); L := array(1..m+n); while i <= m and j <= n do if L1[i] <= L2[j] then L[k] := L1[i]; i := i+1; else L[k] := L2[j]; j := j+1; fi; k := k+1; od; while i <= m do L[k] := L1[i]; i := i+1; k := k+1; od; while j <= n do L[k] := L2[j]; j := j+1; k := k+1; od; convert(L,list); end:
We illustrate the use of this procedure with the following example:
Merge([1,2,6,8],[3,5,7]);
We now provide the pseudocode for the merge sort algorithm.
The description of the merge sort algorithm that we will use is based on a recursive definition. In pseudocode,

If the list, L has only one element, it is sorted in order, so we return L as is.

If L has more than one element, we split the lists into two lists of the same size or where the second list has exactly one more element than the first.

We recursively merge sort these two lists, and merge the two sorted lists together.
MergeSort:=proc(L::list) local First, Second,i, n;
If the list has only one element, return it
if nops(L) = 1 then
print(L);
L; else
The list has more than one element print(L);
n := nops(L); mid := floor(n/2);
Split the lists into two sublists of equal size
First := L[1..mid]; Second := L[mid+1..n];
Merge the result of the Merge sorts of the two lists
Merge(MergeSort(First), MergeSort(Second)); fi; end:
We illustrate the use of the MergeSort procedure by sorting an unsorted list with 100 elements:
MergeSort([8,2,4,6,9,7,10,1,5,3]);
We will now analyze the running time for MergeSort in relation to the running time for BubbleSort. Specifically, we will create a 10000 element unsorted list with random elements, and execute both BubbleSort and MergeSort on this list. This will provide a limited illustration of the running time of these procedure, which the reader should expand upon by reading the theoretical analysis of the text.
To create a random list of 1000 elements, we use the rand and seq commands of Maple as follows:
A:=[seq(rand(), i=1..100)]:
Then, we can use the time command to measure the amount of time required to sort the random list:
st:=time(): BubbleSort(A): time()  st; st:=time(): MergeSort(A): time()  st;
The reader is encouraged to implement other sorting algorithms using Maple and to study the relative complexity of these algorithms when used to sort lists of various lengths. It is also interesting to use animation techniques to illustrate the steps of sorting algorithms. Although we do not do that here, the reader with advanced programming skills is invited to do so. Take special note of the importance of using the right data structure, i.e., lists versus arrays.
5. Spanning Trees
Click here to access a summary of all the Maple code used in this section.
This section explains how to use Maple to construct spanning trees for graphs and how to use spanning trees to solve many different types of problems. Spanning trees have already been used in Chapter 7; they have a myriad of applications. In particular, we will show how to use Maple to form spanning trees using two algorithms: depthfirst search and breadthfirst search. Then we will show how to use Maple to do backtracking, a technique based on depthfirst search, to solve a variety of problems.
To begin, we will discuss how to implement depthfirst search in Maple. As the name of the algorithm suggests, vertices are visited in order of increasing the depth of the spanning tree. The pseudocode is:

Given a graph G, and a root vertex v, consider the first neighbor of v, called w. Add edge to the spanning tree.

Pick x to be a neighbor of w that is not in the tree. Add edge and set w equal to x.

Repeat step (2) until there are no more vertices not in the tree.
The depth first search implementation is as follows:
Depth := proc(G::graph, r) local v, V, N, S,In_Tree; new(S); addvertex(r, S); In_Tree:=[r]; while In_Tree <>[] do v := In_Tree[1]; N:=neighbors(v, G) minus vertices(S); if N = {} then In_Tree := In_Tree[1..nops(In_Tree)1]; next; fi; addvertex(N[1],S); addedge([v,N[1]],S); In_Tree:=[op(In_Tree), N[1]]; od; eval(S); end:
We demonstrate the usage of the depthfirst search procedure with the following example:
new(G1): addvertex(A,B,C,D,E,F,G,H,I,J,K,L,M, G1): addedge( A,B,A,D,B,C,B,E,C,F,D,E, D,H,E,F,E,I,F,G,F,J,G,L, G,J,H,K,H,I,I,J,I,K,M, K, G1); S1:=Depth(G1,E): draw(Tree(E), S1);
Having implemented the depthfirst spanning tree algorithm, we can now modify the Maple code slightly and get a breadthfirst spanning tree. Specifically, the breadthfirst search algorithm operates by examining all vertices at the current depth of the graph before moving downwards to the next level of the graph. Before implementing this algorithm, we give a pseudocode description of the algorithm.

Given a graph G, and a root vertex v, identify the neighbors of v. Call this neighbor set .

Add edges from v to each vertex in that is not already in the spanning tree.

Pick the first vertex from , called w. Consider the neighbors of w; call this set of neighbors .

Repeat step (2) with w substituted in for v, and substituted in for .

If all vertices in have been exhausted, move down to the next level, and repeat step (2).
A Maple implementation is the following, called Breadth;
Breadth:=proc(G::graph, r) local v, N, S, In_Tree; new(S); addvertex(r, S); In_Tree:=[r]; while not(In_Tree=[]) do v := In_Tree[1]; N:=neighbors(In_Tree[1], G) minus vertices(S); for v in N do addvertex(v,S); addedge([In_Tree[1], v],S); In_Tree:=[op(In_Tree), v]; od; In_Tree:= In_Tree[2..nops(In_Tree)]; od; eval(S); end: S2:=Breadth(G1, E): draw(Tree(E), S2);
Notice that the two spanning trees are different even though they are rooted at the same vertex. In particular, the depthfirst search tree has a deep and thin structure, whereas as the breadthfirst search tree has a shorter and wider structure. These graphical representations help to illustrate the algorithm used, and heuristically, we can use the representations to guess whether a depthfirst search or a breadthfirst search has been used.
5.1. Backtracking
Click here to access a summary of all the Maple code used in this section.
Backtracking is a method that can be used to find solutions to problems that might be impractical to solve using exhaustive search techniques. Backtracking is based on the systematic search for a solution to a problem using a decision tree. (See the text for a complete discussion.) Here we show how to use backtracking to solve several different problems, including coloring a graph, solving the nqueens problem of placing n queens on a chessboard so that no queen can attack another queen, and solving the subset sum problem of finding a subset of a set of integers whose sum is a given integer.
The first problem we will attack via a backtracking procedure is the problem of coloring a graph using n colors, where n is a positive integer. Given a graph, we will attempt to color it using n colors in a greedy manner, as done in the section on Graph Coloring in the text. However, when we reach a coloring that does not allow us to color an additional vertex properly, we backtrack, changing the color on an earlier colored vertex and trying again. Here is the pseudocode for our BackColor procedure which carries out this coloring based on backtracking. Here we order the colors as color 1, color 2,..., color n.

Order the vertices of the graph G as .

Assign color 1 to . Set

Assign color c to , where c is the smallest integer so that no neighbor of has been assigned color c

If we can assign such a color to , increment i and repeat step (3).

If we cannot assign any color to , we backtrack, setting and incrementing the color of if possible.

If we do not have a valid coloring, repeat step (5).

Stop when we color all vertices, or we have exhausted all possible colorings.
An implementation of this pseudocode in the following Maple algorithm called BackColor:
BackColor := proc(G::graph,n::integer) local i,k, v, V, cur_vertex, Assigned, Available, used , N, cur_color; V:= convert(vertices(G), list );
Initialize the Assigned and Available colors
for v in V do Assigned(v):=0; Available(v):=[seq(k, k=1..n)]; od; cur_vertex:=1; while cur_vertex >= 1 and cur_vertex <=nops(V) do v := V[cur_vertex];
Assign smallest color to current vertex Gather all neighbors of current vertex
N:=neighbors(v, G); while Assigned(v)=0 and Available(v) <> [] do Used := map( Assigned , N ); if not member( Available(v)[1], Used ) then Assigned(v) := Available(v)[1]; fi; Available(v) := Available(v)[2..nops(Available(v))]; od;
Backtrack if no such color exists
if Assigned(v) = 0 and (Available(v) = []) then printf(`Backtracking on %a %d`, v, Assigned(v)); while (Available(v)= []) and cur_vertex > 1 do Available(v) := [seq(k, k=1..n)]; Assigned(v) := 0; cur_vertex := cur_vertex  1; v := V[cur_vertex]; od; if cur_vertex > 1 then Assigned(v) := 0; else break; fi; else cur_vertex:=cur_vertex+1; fi; od; if not has( map( Assigned , V ), 0 ) then for v in V do printf(`Assign vertex %a color %d`, v, Assigned(v)); od; else printf(`There does not exist a proper vertex coloring`); printf(`with %a colors`, n); fi; end:
We will now try this implementation on a new graph called C1. Notice that the output of the BackColor procedure is the current assignment of colors at any backtracking stage, and the final coloring or indication of the nonexistence of proper coloring upon termination of the procedure.
new(C1): addvertex([E,B,C,D,A], C1): addedge(A,B,A,E,B,C,B,D,B,E,C,D,D,E,C1): BackColor(C1,3);
Next, we will examine the execution of the BackColor procedure on C1 with two new edges added. Notice that there this new graph has as a subgraph;
addedge(A,D,A,C, C1): BackColor(C1,3); BackColor(C1,4);
Another problem with an elegant backtracking solution is the problem of placing nqueens on an chessboard so that no queen can attack another. This means that no two queens can be placed in the same horizontal, vertical, or diagonal line. We will solve this problem using a procedure based on backtracking. We will place queens on the chessboard in a greedy fashion, until either all the queens are placed or there is no available position for a queen to be placed without sitting on the same diagonal, vertical or horizontal line, with a queen that has already been placed.
To make the main procedure easier to understand, we will create a helper procedure that will verify whether a particular placement of queens is valid. If there are two queens on the same row, column or diagonal, then ValidQueens will return false; otherwise, the procedure will return true;
ValidQueens:=proc(Q::matrix, row::integer, col::integer, size::integer) local i,return_value; return_value:=true;
Verify the dimensions are valid
if row > size or col > size then return_value := false; else
Check Queens horizontally Note that main algorithm never places two queens in the same column, so vertical check is not needed
for i from 1 to col1 do if Q[row, i] = 1 then return_value:=false; fi; od;
Check Queens on the two diagonals
for i from 1 to col1 do if row>i then if Q[rowi, coli] = 1 then return_value:=false; fi; fi; if row+i <=size then if Q[row+i, coli] = 1 then return_value:= false; fi; fi; od; fi;
Return the value
return_value; end:
The main procedure for solving the nqueens problem, which will be called NQueens, follows the same control flow as the BackColor procedure, as can be deduced from the inline comments. Specifically, we have an initialization stage, an incremental stage where we try to fill the current column, and a backtracking stage where we backtrack if we cannot place a queen in the current column. The Maple implementation of this procedure follows:
NQueens:=proc(n::integer) local cur_col, cur_row, Q, bad_position, Assigned;
Initialize Queens
Q:=linalg[matrix](n, n, 0); cur_col:=1; Assigned:=[]; while cur_col >= 1 and cur_col <=n do
Assign a Queen to the next column
bad_position := true; cur_row:=0;
does first available position work?
while cur_row < n and bad_position do cur_row := cur_row+1; bad_position := false;
bad if there is a neighbor vertex colored
Q[cur_row, cur_col] := 1; if not ValidQueens(Q, cur_row, cur_col, n) then bad_position := true; Q[cur_row, cur_col] := 0; fi; od;
Backtrack if no available Queen position
if cur_row=n and bad_position then printf(`Backtracking on column`); printf(` %d of %a since stuck`, cur_col, Q); while not ValidQueens(Q, cur_row, cur_col, n) and cur_col > 1 do cur_col := cur_col1; Q[Assigned[cur_col], cur_col]:=0; cur_row := Assigned[cur_col] + 1; Assigned:=subsop(cur_col=NULL, Assigned); od; if cur_col >= 1 and cur_row <= n then Assigned:=[op(Assigned), cur_row]; Q[cur_row, cur_col] := 1; cur_col := cur_col + 1; else cur_col := cur_col  1; fi; else
If Queen placement is currently valid, move to the next column
cur_col:=cur_col+1; Assigned:=[op(Assigned), cur_row]; fi; od; if (cur_col >= 1) then printf(`A proper Queen placement is %a`, Q); else printf(`No Queen placement with %d Queens`, n); fi; end:
We now use the NQueens procedure to solve the nqueens problem when n=3 and n=4;
NQueens(3); NQueens(4);
We consider a third problem which can be solved using backtracking; the subset sum problem. Given a set of integers S, we wish to find a subset B of S such that the sum of the elements of B is a given value M. To use backtracking to solve this problem, we successively select integers from S until the sum of these elements equals M or exceeds M. If it exceeds M, we backtrack by removing the last element in the sum, and we insert a different value.
Before we implement the main procedure, we will create two small helper functions that aid in the manipulation of lists. The first helper procedure, which is called ListSum determines the sum of the elements in a given list.
ListSum:=proc(S::list, Ind::list) local i, T; T:=0; for i from 1 to nops(Ind) do T:=T+S[Ind[i]]; od; T; end:
The second helper function, called ListInd determines a subset of a given list S that is indicated by the positions stored in list J.
ListInd:=proc(S::list, J::list) local i, T; T:=[seq(S[J[i]],i=1..nops(J))]; end:
The main procedure to determine a possible solution to the subset sum problem, called SubSum, follows;
SubSum:=proc(S::list, M::integer) local CurSub, next_index, T, Ind, CurSum,i;
Initialize variables
Ind:=[]; CurSum:=0; i:=1; next_index:=0; T:=S;
Loop until we reach the given sum value
while not (CurSum = M) do printf(`The current subset %a has sum %d`, ListInd(T, Ind), CurSum); next_index:=next_index+1;
If we have reached an impasse, backtrack
if next_index > nops(T) and Ind[nops(Ind)] = nops(T) then Ind:=subsop(nops(Ind)=NULL,Ind); Ind:=subsop(nops(Ind)=NULL,Ind); CurSum:=ListSum(T, Ind); else
if out of values to sum, backtrack
if next_index > nops(T) then next_index:=Ind[nops(Ind)]+1; Ind:=subsop(nops(Ind)=NULL, Ind); CurSum:=ListSum(T,Ind); fi;
If the current subset less than M, then we add the next value to the subset
if CurSum+T[next_index] < M then Ind:=[op(Ind), next_index ]; CurSum:=ListSum(T, Ind); fi; fi;
If we have exhausted the index, set variables to halting values
if Ind=[] then T:=subsop(1=NULL, T); break; fi; od;
Return the list sum
ListInd(T,Ind); end:
We execute this procedure on the Example 6 on page 588 of the text:
SubSum([31,27,15,11,7,5], 39);
The three problems we have attacked using backtracking, coloring graphs, the nqueens problem, and the subset sum problem are representative of the vast number of problems that can be solved using backtracking and the reader will certainly find occasions when the techniques of this section will help solve such problems. (See Exercise 7 at the end of this section, for example.)
6. Minimum Spanning Trees
Click here to access a summary of all the Maple code used in this section.
This section explains how to use Maple to find the minimum spanning tree of a weighted graph. Recall that a minimum spanning tree T of a weighted graph G is a spanning tree of G with the minimum weight of all spanning trees of G. The two best known algorithms for constructing minimum spanning trees are called Prim's and Kruskal's algorithms (although they have an older history); we will develop Maple procedures that implement both of these algorithms here.
We will begin by studying Prim's algorithm, whose pseudocode is outlined on page 594 of the text. Prim's algorithm proceeds by constructing a tree by successively selecting a minimum weight edge that extends this tree from its current set of vertices. The pseudocode is as follows:

Start to build the minimum weight spanning tree T with an edge of minimum weight of the entire graph.

Add to T the edge of minimum weight that is incident to a vertex in T which does not form a simple circuit in T

Repeat step (2) until we have a total of n1 edges in T
To simplify our implementation of Prim's algorithm, we first create a procedure, MinWeight, that determines the edge of minimum weight with exactly one vertex in a given set of vertices.
MinWeight:=proc(G::graph, S::set) local e, i, Candidates, Del, Min_Edge;
Determine the set of adjacent edges
if S=vertices(G) then Candidates:=edges(G) else Candidates := incident(S,G); fi; if Candidates = {} then RETURN(NULL) fi;
Determine the minimum weight edge candidate
Min_Edge:=Candidates[1]; for e in Candidates do if eweight(Min_Edge,G) > eweight(e ,G) then Min_Edge:=e; fi; od; RETURN(Min_Edge); end:
The special case of all vertices of G is included to provide a convenient starting point Prim's algorithm. In this case, we simply return the edge of G of minimum weight. In all other cases, the search is restricted to edges emanating from the subgraph induced by the specified vertices. The implementation depends on the fact that the procedure incident finds all the edges that leave a particular set of vertices. Also, the overall efficiency of the algorithm can be improved by systematically working our way through a sorted list of edges rather than searching anew for edge candidates at every step.
Given the procedure MinWeight, the actual implementation of Prim's algorithm is straightforward. we first initialize the minimum weight tree T to be the tree with just one edge, an edge of least weight. At each step we add an edge of minimum weight that incident with the current tree T.
Prim := proc(G::graph) local i, VT, V, T, e; new(T); V := vertices(G);
Add minimum weighted first edge
e := MinWeight(G,V); addvertex(ends(e, G), T); addedge(ends(e,G), T);
Loop until all n1 edges are added to tree
for i from 2 to nops(V)1 do e := MinWeight(G,vertices(T)); if e = NULL then ERROR(`no spanning tree`) fi;
Add new vertex as well as new edge
addvertex(ends(e,G) minus vertices(T), T); addedge(ends(e,G),weights=eweight(e,G),T); od; RETURN( eval(T) ); end:
We return eval(T) rather than just T to ensure that the actual tree, rather than just its name is passed back.
To test the procedure Prim we find a minimum weight spanning tree of the weighted graph from Example 1 on page 595 of the text. You can construct the graph using the commands
new(City1): addvertex(sf,chic,den,ny,atl,City1): addedge( [sf,ny,sf,chic,sf,den,sf, atl], weights=[2000,1200,900,2200], City1): addedge( [den,chic,den,ny,den, atl], weights=[1300,1600,1400], City1): addedge( [chic,ny,chic,atl, atl, ny], weights=[1000,700, 800], City1):
Then the minimum weight spanning tree is T1 given by
T1 := Prim(City1):
This tree is best viewed as a tree by selecting a particular root and then drawing the tree.
draw(Tree(sf), spantree(T1,sf));
The total weight of its edges can be computed as
total := 0: for e in edges(T1) do total := total + eweight(e,T1) od: total;
Kruskal's algorithm algorithm builds the minimum weight tree by successively adding an edge of least weight that does not form a simple circuit in any of the previously constructed tree fragments. The psuedocode for this algorithm is:

Sort the edges of the graph in ascending order.

Choose smallest weight edge, e

If e creates a cycle in T when added, discard e from the list and repeat step (2)

Add e to the minimum weight spanning tree T

Repeat step (2) until the tree has n1 edges
Before we can implement Kruskal's algorithm, we need to be able to sort edges. As in earlier sections, we can do this using Maple's built in sorting routine by providing a suitable procedure for comparison of any two edges.
The comparison routine required here is subtly more complicated than before because it must use the graph in addition to the edge names inside the comparison. This can be accomplished using a template procedure as follows. A specific graph is substituted for a placeholder in a template.
edgecompare := proc(G::graph) subs(TESTG=eval(G) , proc(a,b) if eweight(a,TESTG) <= eweight(b,TESTG) then true else false fi; end ); end:
By invoking this procedure on a specific graph such as City1, we create a comparison procedure customized to that graph.
comp1 := edgecompare(City1):
It can be used as
comp1(e1,e2);
Now to sort a list of the edges of City1 by weight all we need do is
edgelist := convert(edges(City1),list); edgelist := sort(edgelist,comp1);
The weights of this sorted list are in ascending order, as verified by mapping the eweight command onto the list.
map( eweight , edgelist , City1);
Armed with this sorting routine, we are nearly ready to implement Kruskal's algorithm. At each step of the algorithm, we have an edge e, a collection of trees T, formed from edges of G, and G, and we must determine if the edge e forms a cycle. This is done by finding the components of T, and checking each component to see if both ends of the edge e are in that same component. This is accomplished by the procedure
InComponent := proc(e,T::graph,G::graph) local c,C; C := components(T); for c in C do if ends(e,G) minus c = {} then RETURN(true); fi; od; RETURN(false); end:
It makes use of the fact that the components commands represents each component by a set of vertices.
Now we are ready to implement Kruskal's algorithm.
Kruskal:=proc(G::graph) local E,T,i,n,e; E := convert( edges(G), list); # sort the edges E := sort( E, edgecompare(G));
start building the forest
new(T); i := 0; n := nops(vertices(G)): while i < n and E <> [] do e := E[1]; if InComponent( e , T , G ) then E := subs(e=NULL,E); next; fi;
add new edge to forest
addvertex(ends(e,G),T); addedge(ends(e,G),T); i := i+1; E := subs(e=NULL,E); od; eval(T); # the new tree end:
This algorithm can also be tested on the tree City1. from Example 1 on page 595.
T2 := Kruskal(City1): draw(Tree(sf), spantree(T2,sf));
7. Computations and Explorations
Click here to access a summary of all the Maple code used in this section.

Display all trees with six vertices
Solution
To solve this problem, we use a recursive definition of trees. We know that an empty graph is a tree, and that a graph with a single vertex is a tree. We can then build up larger trees from these smaller trees by taking each vertex and forming a new tree by adding a leaf connected to that vertex. (The reader can verify that this truly creates all trees with one more vertex).
Thus, we shall create a Maple procedure, called ExtendTree, that takes a set of trees on n vertices, and adds a new edge to each tree, returning the resulting set of trees on n+1 vertices. The maple{} implementation is as follows:
ExtendTree:=proc(Trees::set) local i, j, S, t, num_vertices, X; S:={};
Loop over all trees in given set
for i to nops(Trees) do T := Trees[i];
Add new vertex
num_vertices:=nops(vertices(T)); addvertex(num_vertices+1, T);
For each vertex, add new leaf edge
for v in vertices(T) do new(X[i][v]); X[i][v]:=duplicate(T); addedge([v , num_vertices+1], X[i][v]); S:=S union X[i][v]; od; od; S; end:
We will now illustrate how to form all trees on 4 vertices, and leave the determination of all trees of larger size to be determined by the reader;
new(StartingTree): addvertex(1, StartingTree): X:=ExtendTree(ExtendTree(ExtendTree(StartingTree))): draw(Tree(1),X[1]); draw(Tree(1), X[2]): draw(Tree(1),X[3]): draw(Tree(1), X[4]): draw(Tree(1),X[5]): draw(Tree(1), X[6]):

Construct a Huffman code for the letters of the English language based on the frequence of their occurrence in ordinary English text
Solution
This problem can be broken down into two smaller problems. The first problem is to determine how to gather the frequency of occurrence for each letter of the English language. The second problem is how to construct a Huffman code based on this frequency of occurrence.
We already have created the Huffman procedure in Maple that can be used to determine the correct Huffman code given the frequency of occurrence of the English characters. Hence, we have solved the second problem.
To solve the first problem, we can use Maple to scan through a string of text and count the number of occurrences of each letter of the English alphabet. Specifically, we can use strings in Maple in the following manner. Suppose that we have a passage of text which is in lower case and has no punctuation, such as:
input_text:= `the quick brown fox sat down and had lunch with me`;
Then, we can initialize a table indexed on each character of the English language, and then scan through the input_text and count the occurrence of each character.
Initialization
alphabet:=`a bcdefghijklmnopqrstuvwxyz`; for i from 1 to length(alphabet) do freq[substring(alphabet, i..i)]:=0; od:
Count occurrence of each character
for i from 1 to length(input_text) do freq[substring(input_text, i..i)] := freq[substring(input_text, i..i)] + 1; od: freq[a]; freq[e]; freq[q];
To determine the frequency of occurrence of English letters in certain contexts we can run this program on large sample input. We can simply extend our alphabet to include punctuation and any other special characters that are used in the character set. You will find somewhat different frequency distribution for different types of content, such as literature, correspondence, computer programs, electronic mail, and so on. It is worth noting that many books on cryptography (such as Cryptography: Theory and Practice by Douglas R. Stinson, CRC Press, 1995) contain the frequencies of characters in English, and of many other languages. Additionally, this code can be used to count frequency of occurrence of any character set, such as the ASCII character set, the French character set, the Spanish character set, and so on.

Compute the number of different spanning trees of for n=1,2,3,4,5,6. Conjecture a formula for the number of such spanning trees whenever n is a positive integer
Solution
This problem can be solved quite easily using the counttrees command of Maple, which returns the number of unique spanning trees of an undirected graph. Thus, to determine the number of unique spanning trees on we can execute the following Maple statements:
counttrees(complete(1)); counttrees(complete(2)); counttrees(complete(3)); counttrees(complete(4)); counttrees(complete(5)); counttrees(complete(6));
We leave it to the reader to conjecture a formula. A useful hint is to look for a formula of the form , where is a simple function in terms of n.

Compute the number of different ways n queens can be arranged on an chessboard so that no two queens can attack each other for all positive integers n not exceeding 10.
Solution
This problem can be solved by altering the procedure NQueens that was implemented in this chapter. Specifically, when a solution is determined, rather than exiting the procedure, we simply backtrack on that solution, and continue, until all solution paths have been examined. Thus, the procedure will exit only when all solutions have been outputted. We leave it to the reader to alter the NQueens procedure and conjecture a formula for the number of solutions in terms of n for the nqueens problem.

Draw the complete game tree for a game of checkers on a board.
Solution
We will offer a partial solution to this problem; the reader is left to complete the full solution. Specifically, we will create a Maple procedure called MovePiece that will determine all possible new checker arrangements given a specific piece that is to be moved on a given checker arrangement. Once this procedure is created, the reader must determine how to represent these board positions as vertices and edges, how to determine the next level of the game tree, as well as any necessary halting conditions.
The implementation of MovePiece is straightforward: we examine each piece that can be moved, and then determine if we can move the piece forward and to the left or right, depending on the piece's current board position and whether there is a piece occupying a possible new position. Also, we will determine if a piece can jump and capture an opponents piece, depending on the board space and position of the opponent's positions. Additionally, we will examine whether a piece is a king, in which case, the piece can move both forwards and backwards on the checkerboard.
We now give the Maple implementation of MovePiece. Inline comments are provided to make this code easier to understand.
MovePiece:=proc(A::matrix, piece::integer) local i, j, k, cur_column, is_king, S, Temp, direction;
Initialize values, depending on the piece value
S:=[]; if piece = 1 then direction:=1; else direction:=1; fi;
Examine all possible positions on board
for i from 1 to 4 do for j from 1 to 4 do
If we have found a piece, determine whether or not it is a King
if abs(A[i,j])=piece then if A[i,j] < 0 then is_king:=1; else is_king:=0; fi;
If the piece is a King, then examine both forward and reverse directions
for k from 0 to is_king do if k>0 then direction:=1*direction; fi;
Examine possible new positions to see if they are still on the board
if i+direction >= 1 and i+direction <= 4 then for cur_column from 1 to 1 by 2 do if jcur_column >=1 and jcur_column<=4 then
Determine if the position is free
if A[i+direction, jcur_column] = 0 then
Move a single position
Temp:=copy(A); Temp[i,j]:=0; Temp[i+direction, jcur_column]:=piece; S:=[op(S), copy(Temp)]; elif abs(abs(A[i+direction,jcur_column]) piece)=1 then
We may be able to jump a piece
if (i+2*direction >=1 and i+2*direction<=4) and (j2*cur_column >=1 and j2*cur_column<=4) then
Jump a piece
if A[i+2*direction, j2*cur_column] = 0 then Temp:=copy(A); Temp[i,j]:=0; Temp[i+direction, jcur_column]:=0; Temp[i+2*direction, j2*cur_column] :=piece; S:=[op(S), copy(Temp)]; fi; fi; fi; fi; od; fi; od; if is_king=1 then direction:=1*direction; fi; fi; od; od;
Check for Kings
for i from 1 to nops(S) do for j from 1 to 4 do if S[i][1,j] = 1 then S[i][1,j]:=1 fi; if S[i][4,j] = 2 then S[i][4,j]:=2 fi; od; od;
Return list of new board arrangements
S; end:
To examine this procedure, we will create an initial checkerboard arrangement, called A, using the matrix function of Maple.
A:=linalg[matrix](4, 4, [[2,0,2,0],[0,0,0,0],[0,0,0,0],[0,1,0,1]]);
Then, we examine the execution of this procedure on several examples:
8. Additional Exercises

Using page 546 of the text as reference, write a Maple procedure for finding the eccentricity of a vertex in an unrooted tree, and for finding the center of an unrooted tree.

Develop a Maple procedure for constructing rooted Fibonacci trees (see page 547 of the text)

Develop a Maple procedure for listing the vertices of an ordered rooted tree in level order (see page 604 of the text)

Construct a Huffman code for the letters of French, based on their occurrence in ordinary French text. The frequency of letters in French is as follows:
E: 18%, A: 8%, I: 7%, U: 6%, O: 5%, Y: 0.2%, S: 8%, N: 8%, T: 7%, R: 7%, L: 6%, D: 4%, C: 3%, M: 3%, P: 2%, V: 2%, F: 1%, Q: 1%, G: 1%, B: 0.9%, H: 0.6%, X: 0.4%, J: 0.3%, Z: 0.06%

Develop a Maple procedure for producing degreeconstrained spanning trees, as outlined on page 604 of the text. Use this procedure on a set of randomly generated graphs to attempt to construct degreeconstrained spanning trees where each vertex has degree no larger than 3

Use Maple to analyze the game of checkers on square boards of different sizes via the technique of game trees

Develop Maple procedures for finding a path through a maze using the technique of backtracking

Use Maple to generate as many graceful trees as possible (see page 605 of the text). Can you make any conjectures for this evidence?

Implement the quick sort in Maple.

Implement the selection sort in Maple.

Implement the insertion sort in Maple.

Use Maple to compare the complexity of different sorting algorithms when sorting the same list of numbers for various initial lists of numbers.

Alter the postfix expression evaluator to handle prefix expressions.

Use Maple to animate the steps of different sorting algorithms. Specifically, show each step of the algorithm with one second pauses between movements of elements.

Modify the code for Prim and Kruskal so that the edges chosen are displayed as they are selected, and compare the choices of edges.

Use the procedure provided to count the frequency of occurrence of characters to determine the frequency of characters in various types of English content using relatively large sample input. For example, you might want to use electronic mail messages, computer code, newspaper articles, fiction, and so on.