Graph Representations and Traversals

(a) Write pseudo-code for an algorithm that performs depth first search of a directed graph: G - (V, E) and prints out all of the edges visited. [10 marks] (b) The following questions relate to traversals of directed graphs i. The graph-search algorithms shown in lectures always keep track of visited nodes because failing to to do so can result in non termination. Draw a graph that will lead to non-termination of Depth-First-Search if we fail to keep track of nodes already vis- ited. [3 marks] ii. Under what conditions can the Single-Source-Shortest-Path prob- lem be solved using Breadth-First-Search? [2 marks] (c) When is it advantageous in terms of memory-use to store a graph as an adjacency list rather than an adjacency matrix? Briefly justify your answer. 2 marks]