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

Example

Consider the following arbitrary graphical representation of vertices, and corresponding (directed) edges.

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

Representation: Adjacency List

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
]

Representation: Adjacency Set

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
]

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