1. The simple graph small.txt (which comes with an initial line "11" for the vertex count).
   

   [The answer below on the left may be what you have. On the left, the upper number is the d, or "discovered" field, while the lower number is the f or "finished" field. You were supposed to use recursion, so you shouldn't have the one on the right. In the non-recursive (using a stack) version, the values of the f field don't have the same applications as the recursive version.]

   Using Recursion, Start = 0	Using a Stack, Start = 0

   [You weren't told which vertex to use as the start. Here are 10 more such searches, using different start vertices.]

2. The 48-capitals graph. [We already saw examples of DFS with 48-capitals: DFS.]

Your run for each graph above must include:

1. The depth-first search. This part requires no output, although you can accomplish part b either during the seach or as a separate step.
2. A printout of the list of vertices along with their vertex data, that is, values of the d, f, and pi fields for each vertex, showing the course of the search and defining the depth-first spanning tree. Everything about the search from your chosen start vertex is implicit in this data.

1. First is the dag in Figure 22.7 on page 613. For use in our program, I've numbered the 9 vertices as: undershorts:0, socks:1, watch:2, pants:3, shoes:4, belt:5, shirt:6, tie:7, jacket:8. ["Undershorts"! What the hell? I looked this up in my paper dictionary, since it's obviously some archaic term. It said "See short 4b". OK, under that reference, it said: "pl: short drawers". What? This sounds actively scary. What is this guy wearing?]
   

   Notice that this is a directed graph, so we don't enter edges in both directions as we did before. It is also acyclic, meaning that there are no non-trivial loops. This is what your text calls a "dag", a "directed acyclic graph". The DFS has to start over again at several vertices, and the spanning tree is a spanning forest consisting of several trees. Here is a file with the edges: clothing.txt, with an initial record holding "9", the number of vertices.

   In order to carry out the topological sort, you add a single print statement after the part of the DFS that gives each f field its value, printing the vertex that gets assigned this value. This will print the vertices in reverse order from the order of topological sort. (See your text, page 613. You don't need to bother putting them into a linked list as your text suggests.) Notice that in general there will be many different correct topological sorts, so you should not expect to get the order shown in the image above. (In the image above, the finish time for "jacket" is 4 and it comes first. Next is the finish time for "tie" which is 5, and so forth, giving the topological sort backwards.)

2. The second dag for a DFS and topological sort is from Figure 22.8 on page 615. The figure shows vertices labeled with letters from m to z, but in the data below, these are integers from 0 to 13.
   

   Here is a files with the edges: dag.txt with an initial record holding "14", the number of vertices. In this case the spanning tree is again a spanning forest, with three separate trees. Here again you should give the vertices in reverse order of a topological sort.

For full credit you must show the relaxation steps and show how the values for distance and predecessor change to the final values. [I will give an answer to this before the final. For practice with Dijkstra's algorithm, here are 3 other graphs to process: practice graphs.]

[Some students found my answer below obscure, so let me explain it:
The source vertex is a.
Initial weights on vertices are 0 on a and ∞ on all others.
Make up a min priority queue of all vertices, priority is the weight.
The third line of the table (labeled "Initial") gives this initial priority queue, along with the predecessor vertices, all nil.
The order in this line is just alphabetic by vertex name, and so the order has no significance.
At each stage, Dijsktra's algorithm removes the vertex with lowest "distance" number. Initially this is a.
The algorithm does a relax step to update distances. This step also gives new values to predecessor vertices.
The result of the first step is given in the fourth line, labeled "a".
The vertex removed is labeled with a "*", so it's gone for good from the priority queue.
Again do a "remove", "relax", and "update", removing the vertex b, and producing the next line. (b has the lowest value still in the queue).
Notice that the second relax step changes d's values from "8,a" to "7,b".
Continue by removing d, and so on until the queue is empty.]

Action	Contents of Priority Queue (* = removed)
Remove & Relax	a, π	b, π	c, π	d, π	e, π	f, π
Initial	0, nil	∞, nil	∞, nil	∞, nil	∞, nil	∞, nil
a	0, nil *	5, a	∞, nil	8, a	∞, nil	∞, nil
b	0, nil *	5, a *	15, b	7, b	9, b	∞, nil
d	0, nil *	5, a *	15, b	7, b *	9, b	∞, nil
e	0, nil *	5, a *	10, e	7, b *	9, b *	14, e
c	0, nil *	5, a *	10, e *	7, b *	9, b *	12, c
f	0, nil *	5, a *	10, e *	7, b *	9, b *	12, c *