[SOLVED] Csc6013 week 4 worksheet

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.