Problem $3)$ Yet another one: Topological Sort! $[25$ pts$.]$

In this question, you are asked to topologically sort the vertices in the directed

acyclic graph $($DAG$)$ given on the left below. We also show the adjacency list

representation of this DAG on the right below. You should note that the vertices

adjacent to a particular vertex are stored in increasing order in this adjacency list.

Please follow the instructions carefully for questions $3\mathrm{.}1$ and $3\mathrm{.}2.$

$3\mathrm{.}1.$ Find a topological ordering by using a queue data structure in the linear time

$($i$.$e$.O(|V|+|E|))$ algorithm discussed in class. Make sure to examine the vertices

adjacent to a node in the order they appear on the corresponding singly linked lists.

Note that since you need to use a queue data structure, you should process the

vertices with in$-$degree zero in a FIFO $($First$-$In First$-$Out$)$ order. $(15$ pts$.)$

$3\mathrm{.}2.$ Find a topological ordering by using a stack data structure instead of a queue

this time. Make sure to examine the vertices adjacent to a node in the order they

appear on the corresponding singly linked lists. Note again that since you need to use

a stack data structure, you should process the vertices with in$-$degree zero in a LIFO

$($Last$-$In First$-$Out$)$ order. $(10$ pts$.)$