Exercise

Exercise topological sort $(15$ points$)$

Using the pseudocode below, perform a topological sort on this DAG:

TopoSort $(G)$

Create postvisit stack

for $v=0$ to $n-1$

if $v$ is not marked then

Call DFS $(v)$

while postvisit stack is not empty

$v=$ pop from postvisit stack

print $v$

$DFS(v)$

mark $v$

for every edge $vu$

if $u$ is not marked then

Call DFS $(u)$

push $v$ onto postvisit stack

The answer is a list of the vertices as printed by the above code.