Read CLR ch. 25, 26.1-3.
(i) exist(u,v) -
test if edge (u,v) is in the graph
(ii) insert(u,v) - insert edge (u,v)
(iii) delete(u,v) - delete edge (u,v)
(iv) out(u) - output all edges exiting vertex u
(v) in(u) - output all edges entering vertex u.
Let n be the number of vertices, m the number of edges, and outdegree(u) and indegree(u) the number of vertices leaving and entering vertex u, respectively.
(a) Suppose you use an adjacency matrix to represent the graph. How much time does each
(b) Suppose you use the adjacency list data structure as described in class. How much time does each operation require?
(c) Design a data structure that combines the features of the adjacency list and adjacency matrix representations in which operations (i), (ii), and (iii) take time O(1) and operations (iv) and (v) take time O(outdegree(u)) and O(indegree(u)), respectively.