NAMES:

LOGINS:

PRECEPTS:

COS 226 Exercises on Digraphs

Reference: Chapter 4.2 in Algorithms, 4th edition.


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