NAME:

PRECEPT:

LOGIN:

COS 226 Exercises on Digraphs

1. Give the order in which DFS first visits each vertex in the following graph. 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
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. 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
Use the "standard" adjacency list representation, as described above.