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

Consider the following graph representation

  b U+2192 →

Example: Adjacency Lists

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

Example: Adjacency Sets

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

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