Compsci 100E, Spring 2011, Classwork 16

The graph below is used in several questions.

Draw diagrams for both the adjacency list and adjacency matrix representations of the graph with directed edges as shown above. For the adjacency matrix use either 0 to indicate no edge and 1 to indicate an edge between the vertices whose matrix entry is [r,c].
Write out a possible vertex ordering for both depth-first and breadth-first traversals of the graph with directed edges as shown above starting at vertex 0 (there's more than one correct answer for each).
In the adjacency-list representation of a directed graph (with E edges and V vertices), what is the big-Oh complexity of how long does it take to compute the out-degree of every vertex (combined time)? How long does it take to compute the in-degree of every vertex (combined time)? Give your answers using notation like O(VE) or O(V) in terms of both V and E. Briefly justify your answers.
```
name: __________________________   login: _____________

name: __________________________   login: _____________

name: __________________________   login: _____________
```