[prev] 26 [next]

Array-of-edges Representation (cont)

Cost of operations:
  • initialisation: O(1)   (malloc GraphRep and edges array)
  • insert edge: O(E)   (assuming edge array has space)
  • delete edge: O(E)   (need to find edge in edge array)
If array is full on insert
  • malloc a bigger array, copy edges across ⇒ still O(E)
If we maintain edges in order
  • use binary search to find edge ⇒ O(logE)