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 vertices incident from 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 vertices incident from v in increasing order.)

digraph 

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




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




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