Graph Representations

Graph Representations in Algorithms II

Introduction to Graph Representations

• In the context of running times of graph algorithms, the input graph's storage method significantly affects performance.

Adjacency Matrix Representation

• One widely-used representation for a graph G = (V, E) is the adjacency matrix.

  • Definition of Adjacency Matrix:

  • Let V = {v1, v2, …, vn} be the set of vertices.

  • The adjacency matrix A is defined such that:

    • $A<em>{i,j} = \begin{cases} 1 &amp; \text{if there is an edge from } v</em>i \text{ to } v_j \ 0 &amp; \text{otherwise} \end{cases}$

  • Example Matrix:

  • Given vertices v1, v2, v3, v4, v5, a possible adjacency matrix is:
    $A = \begin{pmatrix} 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \ 1 &amp; 0 &amp; 1 &amp; 0 &amp; 0 \ 1 &amp; 1 &amp; 0 &amp; 1 &amp; 0 \ 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 \ 1 &amp; 0 &amp; 0 &amp; 1 &amp; 0 \end{pmatrix}$

Performance of Adjacency Matrix

• Time Complexity:

  • Space Required: Storing the matrix takes $Θ(|V|^2)$ space.

  • Adjacency Query: Checking if an edge exists between two vertices (u, v):

  • $Θ(1)$ time.

  • Neighbourhood Query: Finding the set of neighbours for a given vertex, say u:

  • $Θ(|V|)$ time.

Adjacency List Representation

• An alternative storage mechanism is the adjacency list.

  • Definition of Adjacency List:

  • Represented as an array of linked lists where each list Li contains vertices vj such that the edge (vi, vj) exists.

  • Example representation for vertices v1, v2, v3, v4, v5:

    • $L<em>1 = [2, 3], L</em>2 = [1, 4], L<em>3 = [1, 5], L</em>4 = [3, 5], L_5 = [2, 4]$

• Time Complexity:

  • Space Required: Storing arrays of lists takes $Θ(|V| + |E|)$ space.

  • Adjacency Query: Checking if edge (u, v) exists:

  • $Θ(d(u))$, where $d(u)$ is the degree of vertex u.

  • Neighbourhood Query: Finding neighbours of vertex u:

  • $Θ(d(u))$ time.

Comparison of Adjacency Matrix vs Adjacency List

Advantages of Adjacency Matrices

• Fast adjacency queries for all possible graphs.

Advantages of Adjacency Lists

• Fast degree queries for sparse graphs.

• Lower space requirement for sparse graphs.

• Can utilize linear algebra for fast algorithms.

• Using hash tables can drop adjacency queries to average $O(1)$ expected time.

Practical Use Cases

• Generally, in practice, adjacency lists with hash tables are preferred over matrices unless very specific conditions justify the use of matrices.

  • Example conditions may include having a dense graph where the matrix representation is more space-efficient.

Implicit Graphs

• In scenarios like Google's PageRank algorithm, where incoming and outgoing links determine a site's importance:

  • The graph does not need to be stored explicitly, rather, neighbours of a site can be listed efficiently in $O(d(v))$ time.

  • The interface resembles that of adjacency lists while avoiding the need for physical storage of the graph.

Loops and Multiple Edges in Graphs

• Sometimes graphs may include:

  • Loops connecting vertices to themselves.

  • Multiple edges existing between pairs of vertices.

• Such graphs are termed multigraphs.

  • Algorithms designed for simple graphs usually extend to these multigraphs, though visualization can become complex.

  • For this course, a focus will remain on standard, or simple, graphs without loops or multiple edges.