[prev] [index] [next]

Exercise #10 (cont)

Storage cost: V list ptrs + 2*E nodes ≅ O(V+E)

Cost of operations   (if VLists unsorted):

  • initialisation: O(V)   (initialise VLists)
  • insert edge: O(V)   (insert vertex into list, if not there)
  • delete edge: O(V)   (need to find vertex in list)
  • isConnected: O(V)   (need to find vertex in list)