Let G be a graph with five vertices, A, B, C, D, and E, and the following nine edges:
  A has a single edge going outwards, to C
  B has two edges going outwards to C and D
  C has a single edge going outwards, to A
  D has two edges going outwards to E and A
  E has three edges going outwards to A, B, and C

1. List an order in which the vertices might be visited by a breadth-first search that starts at vertex E.

2. Draw a depth-first-search forest for a depth-first search that loops through the vertices in alphabetical order, performing a recursive search for each vertex that has not yet been visited when the loop reaches it.

3. For the depth-first search you performed in question 2, what are the dfsnum and lowlink numbers that the algorithm computes for each vertex?

4. What are the strongly connected components of this graph?

5. In the lecture we covered Tarjan's algorithm for strongly connected components, an algorithm that computes these components in a single depth-first traversal of the input graph by using dfsnum and lowlink numbers. An alternative algorithm is Kosaraju's algorithm (http://en.wikipedia.org/wiki/Kosaraju's_algorithm), a simpler algorithm that uses two depth-first traversals. The first depth-first traversal in Kosaraju's algorithm does a standard depth-first search in which, at each vertex v, the outgoing edges from v are searched recursively. The second depth-first traversal instead searches recursively the incoming edges at each vertex. Explain why Kosaraju's algorithm does not fit well with the graphs derived from the pages and links on a web site.