NAME:

PRECEPT:

LOGIN:

COS 226 Exercises on Digraphs

1. Give the order in which DFS first visits each vertex in the following digraph. This is called the preorder. 
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
Iterate through the adjacency lists in increasing order.












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
















3. Give the order in which DFS last visits each vertex in the following DAG. This is called the postorder. Use this ordering to topologically sort the following DAG. 

0-5 0-6 1-4 2-3 2-6 2-9 3-7 3-8 4-3 4-9 5-2 6-4 7-8
Iterate through the adjacency lists in increasing order.