NAMES:

LOGINS:

PRECEPTS:

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

digraph 



         preorder    0                            
                    ---  ---  ---  ---  ---  ---  ---  ---




2. 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.)

digraph 

        postorder                                            0
                    ---  ---  ---  ---  ---  ---  ---  ---  ---  ---




3. Use the postorder from the previous question to topologically sort the DAG. 




topological order         0                             
                    ---  ---  ---  ---  ---  ---  ---  ---  ---  ---