COS 226 Exercises on Digraphs

NAMES:

LOGINS:

PRECEPT:

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. (Iterate through the neighbors of v in increasing order.)

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

3. Give the order in which DFS finishes visiting each vertex in the following DAG. This is called the postorder. (Iterate through the neighbors of v in increasing order.) Use this ordering to topologically sort the following DAG.