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)
|