DFS – Breadth First Search using the brute force algorithm as seem in class
Consider the graph below:
1) Represent this graph using an adjacency list. Arrange the neighbors of each vertex in alphabetical order.
– list the triplets for this graph in the form (A, B, 1), where there is a edge from vertex A to vertex B;
– Note that this graph is directed, unlike the one presented in class.
β’ (A, E, 1), (A, H, 1)
β’ (B, A, 1)
β’ (C, F, 1), (C, G, 1)
β’ (D, A, 1), (D, E, 1)
β’ (E, C, 1)
β’ (F, D, 1), (F, E, 1)
β’ (G, B, 1), (G, E, 1)
β’ (H, D, 1)
2) Trace the DFS execution by adapting the code to deal with a directed graph (remove lines 7 and 8) and instrumenting it to print every time a recursive call is made and a vertex is visited:
– Each time a recursive call is made for vertex A, print: DFS called for vertex A;
– Each time a vertex A is visited print: Vertex A visited and received the stamp β<count>β and the current array V.
