Todai Entrance Exam: Subject 2018 – Problem 3

(1) AEFDG

(2) BCAEFDG

(3) Real-world problem: Task scheduling. If there are many dependent tasks to do then topological sort will point out the order of tasks to be completed (reference).

(4) function DFS: Replace “print u” in function DFS2 for “s.push(u)”.

(5)

The above code block visited each node of the graph once (thanks to the code line “visited[v] != TRUE”) so the time complexity of this code block is O(| V |).

As s has | V | values corresponding to | V | nodes so the time complexity of this code block is O(| V |).

Overall, the time complexity of the algorithm shown in Fig. 5 is O(2|V|) = O(|V|).

(6) For each v of V, we can use breadth-first search to traverse the graph (a node can be visited once) starting from v and have a list L_{v} to store the values of the child nodes in last-in last-out fashion. We then concatenate these lists L_{v} into a big list L in last-in first-out fashion (values of firstly created L_{v} will be in the last positions of L). We then traverse and print out the values of the list L in the forwarding direction. The time complexity of this algorithm is O(| V |) as each node is visited only once.


Facebooktwittergoogle_plusredditpinterestlinkedinmail

Leave a Reply

Your email address will not be published. Required fields are marked *