Source code online books for professionals by professionals

Listing 2-2.  Adjacency Lists
a, b, c, d, e, f, g, h = range(8)
N = [
    [b, c, d, e, f],    # a
    [c, e],             # b
    [d],                # c

---

Chapter 2 
■
 the BasiCs
26
    [e],                # d
    [f],                # e
    [c, g, h],          # f
    [f, h],             # g
    [f, g]              # h
]
 
It might be argued that this representation is really a collection of adjacency arrays, rather than adjacency lists 
in the classical sense, because Python’s list type is really a dynamic array behind the covers; see earlier “Black Box” 
sidebar about list. If you wanted, you could implement a linked list type and use that, rather than a Python list. That 
would allow you asymptotically cheaper inserts at arbitrary points in each list, but this is an operation you probably 
will not need, because you can just as easily append new neighbors at the end. The advantage of using list is that it is 
a well-tuned, fast data structure, as opposed to any list structure you could implement in pure Python.
A recurring theme when working with graphs is that the best representation depends on what you need to do 
with your graph. For example, using adjacency lists (or arrays) keeps the overhead low and lets you efficiently iterate 
over N(v) for any node v. However, checking whether u and v are neighbors is linear in the minimum of their degrees, 
which can be problematic if the graph is dense, that is, if it has many edges. In these cases, adjacency sets may be the 
way to go.
Tip
 
■
  We’ve also seen that deleting objects from the middle of a python 
list
 is costly. Deleting from the end of a 
list
 
takes constant time, though. if you don’t care about the order of the neighbors, you can delete arbitrary neighbors in 
constant time by overwriting them with the one that is currently last in the adjacency list, before calling the 
pop
 method.
A slight variation on this would be to represent the neighbor sets as sorted lists. If you aren’t modifying the lists 
much, you can keep them sorted and use bisection (see the “Black Box” sidebar on bisect in Chapter 6) to check for 
membership, which might lead to slightly less overhead in terms of memory use and iteration time but would lead to a 
membership check complexity of Q(lg k), where k is the number of neighbors for the given node. (This is still very low. 
In practice, though, using the built-in set type is a lot less hassle.)
Yet another minor tweak on this idea is to use dicts instead of sets or lists. The neighbors would then be keys in 
this dict, and you’d be free to associate each neighbor (or out-edge) with some extra value, such as an edge weight. 
How this might look is shown in Listing 2-3, with arbitrary edge weights added.