Algorithm: Graph Representation

Overview

Adjacency List

An Adjacency list describes a graph representation, using unordered lists. Specifically, each vertex within the graph representation, consists of a set of neighbors (list).

Graphical Representation

Consider the following arbitrary example of vertices, and corresponding edges.

    b ---> c
   ^        ^
  /          \
 /            \
a <----------> d

Adjacency Lists

The following is the adjacency list representation of the given graph:

a, b, c, d = range(4)
N = [
    [b, d], # a
    [c],    # b
    [a, c]  # d
]

Adjacency Sets

The following is the adjacency list representation of the given graph:

a, b, c, d, e, f, g, h = range(8)
N = [
    {b, d}, # a
    {c},    # b
    {a, c}  # d
]

Note: since sets (and dicts) implement a hashing mechanism, accessing a specific index within a set (or dict) is on average constant time O(1), assuming the hashing function used is sufficient.

Note: since lists do not implement a hashing function, for pure iteration (without index lookups), lists are significantly faster.

Adjacency Matrix

Incidence Matrix

Multigraphs

Trees