Digraph Representation (cont)
Costs of representations:
(where degree deg(v) = #edges leaving v)
| | array
of edges | adjacency
matrix | adjacency
list |
| space usage | E | V2 | V+E |
| insert edge | E | 1 | 1 |
| exists edge (v,w)? | E | 1 | deg(v) |
| get edges leaving v | E | V | deg(v) |
Overall, adjacency list representation is best
- real graphs tend to be sparse
(large number of vertices, small average degree deg(v))
- algorithms frequently iterate over edges from v
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}