NAME:

PRECEPT:

LOGIN:

COS 226 Exercises on Digraphs

1. Give the preorder and postorder numbers when you run DFS on the following digraph. 
0-1 1-2 1-7 2-0 2-4 3-2 3-4 4-5 4-6 4-7 5-3 5-6 7-8 8-6 8-7
Use the "standard" adjacency-lists representation. Recall that each edge is inserted at the beginning of the adjacency list of each vertex, so the order or each adjacency list is the reverse of the original input.












2. Give the transitive closure matrix of the digraph in the previous question.











3. [Exercise 19.103] Show, in the style of Figure 19.26, the process of topologically sorting with the source queue algorithm (Program 19.8) the DAG 

3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4 4-3 2-3
The queue is a standard FIFO queue.