### 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.