1.

2. 3.

(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. (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 ii. Under what conditions can the Single-Source-Shortest-Path prob- lem be solved using Breadth-First-Search? (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