CPS 100, Fall 2003, Recitation Warmup

Graph Structures

1. Draw diagrams for both the adjacency list and adjacency matrix representations of the graph with directed edges shown below.

   

2. Write out a possible vertex ordering for both depth-first and breadth-first traversals of the graph with directed edges starting at vertex 0.

3. Describe how each of the following problems may be represented as a graph (i.e. what are the vertices and edges? If necessary, what are the edge weights?):
   1. Internet
   2. highway map
   3. course scheduling for major
   4. appointment scheduling
   5. dating service
   6. flight schedules
   7. maze
   
   
4. For each of the problems above, justify whether to use an adjacency matrix or list implementation for the given graph.

   Ladder structures

5. The code in function breadth in both the programs laddergraph.cpp and laddermatrix.cpp does a breadth first search and stores predecessor indexes in the vector path in that function. Assume a modified version of this function returns this path vector, starting from an initial vertex and visiting all reachable vertices. Using this vector, and the index of the vertex that represents from in the call to breadth, write a function that prints the names of the vertices that are n steps from the starting vertex, i.e., if n == 1 the function would print the names of adjacent vertices to the starting vertex. void nsteps(Graph * g, int n, const string& start) // pre: g is initialized, 0 < n // post: prints names of all vertices n steps from start { tvector<int> list = reachAblePaths(g, start); int startIndex = g->getNum(start); }