Representations of Graphs - rFronteddu/general_wiki GitHub Wiki

There are two standard ways of representing a graph G = (V,E):

  1. Adjacency List: Efficient for sparse graphs (when |E| << $|V|^2$
  2. Adjacency Matrix: Useful for dense (|E| ~ $|V|^2$) graphs or when we need to quickly check if an edge exists between two vertices.

Adjacency-list representation

In this approach, each vertex u in V has a list Adj[u], which contains all vertices v such that there is an edge (u,v) in E.

  • Directed Graph: The sum of the lengths of all adjacency lists equals |E|, as each edge (u,v) appears once in Adj[u]
  • Undirected Graph: The total length is 2*|E|, since an edge (u,v) appears in both Adj[u] and Adj[v].

Advantages:

  • Compact and flexible for sparse graphs.
  • Easily extendable for variants like weighted graphs, where edge weights can be stored in the list.

Disadvantages:

  • Checking for the existence of an edge (u,v) requires searching the list, which can be inefficient.

Adjacency Matrix representation

The adjacency matrix is a |V| x |V| matrix A where:

  • A[i,j] = 1 if there is an edge (i,j) in E, and 0 otherwise.
  • Memory Requirement: O($|V|^2$), regardless of the number of edges.

For undirected graphs, the matrix is symmetric ( A= $A^T$ ), and in some cases, only half of the matrix need to be stored.

Advantages:

  • O(1) access to whether an edge exists between two vertices.
  • Suitable for dense graphs

Disadvantages:

  • Memory-intensive, especially for sparse graphs.
  • Inefficient in space for graphs with few edges.