CS 163, Spring 2012, Homework 1, due Thursday, April 12

  1. Describe the sequence of recursive calls made by the depth first search algorithm for the graph shown below, starting from vertex A. (When the algorithm has a choice of more than one vertex, order the choices alphabetically.)

  2. (From http://commons.wikimedia.org/wiki/File:Directed_graph,_cyclic.svg.)

  3. Describe the sequence in which the vertices of the same graph would be processed by a breadth first search starting at A.

  4. Write down an adjacency matrix for this graph.

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

  6. For your depth first ordering from question 1, write down the depth first search index numbers and the lowlink numbers for each vertex, as computed by Tarjan's strongly connected component algorithm. (Vertex A should have index 0.)