[prev] 43 [next]

Digraph Representation (cont)

Costs of representations:    (where degree d(v) = #edges leaving v)

Representation  Space  Add edge  Exists
edge (v,w)?		  Get edges
leaving v
Adjacency matrix  V2  1  1  V 
Adjacency lists  V+E  d(v)  d(v)  d(v) 
Adjacency sets  V+E  d(v)  log(d(v))  d(v) 

Overall, adjacency sets representation (using sorted arrays) is best

  • real graphs tend to be sparse   (large V,  small average d(v))
  • algorithms frequently iterate over edges from v