Programming for fun and profit

Programming tutorials, problems, solutions. Always with code.

Graph representation

Graphs are fundamental data structure that help to solve many algorithmic problems. In this post we show different graph representations and their properties.

Quick intro to Graphs

Graph is a data structure, which consists of nodes/vertices and connections/edges between them. Just think of it as cities connected with roads or as people connected in social network (like FB). Cities/users are nodes/vertices and connections between them are… connections or edges. These connections can be in one direction (like one-direction road) or bidirectional. Graph where connections/edges have only one direction is called directed graph, otherwise it is called undirected graph.

Graph Representations

Graphs can be represented in three ways: edge list, adjacency matrix, adjacency lists. Of these 3 representations, graphs as adjacency matrix or lists are the most common.
When choosing graph representation, consider the following things:

  1. Memory requirements – space needed to represent a graph.
  2. How fast can we determine whether an edge exists in the graph.
  3. How fast is to find neighbors of a vertex.

Let’s consider the following rail map as graph:

  1. Barcelona has direct train to Berlin.
  2. Berlin has direct train to Warsaw.
  3. Berlin has direct train to Cracow.
  4. Barcelona has direct train to Budapest.
  5. Budapest has direct train to Cracow.
  6. Cracow has direct train to Warsaw.

Our enumerated cities/nodes/vertices are:

  1. Barcelona.
  2. Berlin.
  3. Budapest.
  4. Cracow.
  5. Warsaw.

Graph represented as Edge List

In this representation we store only connections/edges between graph vertices. So in the rail map example it would just a list of connections between the cities:

[[1, 2]  // Barcelona -> Berlin
 [2, 5]  // Berlin    -> Warsaw
 [2, 4]  // Berlin    -> Cracow
 [1, 3]  // Barcelona -> Budapest
 [3, 4]  // Budapest  -> Cracow
 [4, 5]] // Cracow    -> Warsaw

Edge List properties

  1. Space requirement is Teta(E).
  2. Finding edge in such graph takes O(E) time or O(lg E), when the list of edges is sorted (because Binary Search can be used in that case).
  3. To find all neighbors in unsorted list you need to check every edge to see if it comes from the given vertex – O(E). For sorted, count edges starting with the given vertex.

Adjacency matrix

It just means that a graph is a vertex by vertex table/matrix, where each (i,j) position contains 1 when there is an edge between vertices i and j. Else the value is 0. For weighted graph (those where connections have weights – e.g. miles between cities) the value is weight when there is an edge between (i,j) and some special value (possibly null), when there is no edge.

  Barcelona Berlin Budapest Cracow Warsaw
Barcelona 0 1 1 0 0
Berlin 0 0 0 1 1
Budapest 0 0 0 1 0
Cracow 0 0 0 0 1
Warsaw 0 0 0 0 0

As you can see graph adjacency matrix requires a lot of space, even when there are not many edges (graph is sparse) or is symmetric (undirected graphs are symmetric, because edge(i,j) is the same as edge(j,i)), so it’s a waste of memory.
This representation often occurs in 2D games, like Pacman, where there is a maze and you need to find the best way (possibly shortest) somewhere. Valid places in a maze are vertices in the graph and when they are next to each other, they are connected (there is an edge between them).

Adjacency matrix properties

  1. Space requirement is Teta(VxV).
  2. Edge lookup is in constant time – O(1).
  3. Finding neighbors is O(V) – need to check every column for row V.

Adjacency lists

Combines adjacency matrices with edge lists. For each vertex i store an array of vertices adjacent to it. Adjacent vertices may be sorted for fast retrieval.

  [2, 3], // Barcelona -> [Berlin, Budapest]
  [4, 5], // Berlin    -> [Warsaw, Cracow]
  [4],    // Budapest  -> [Cracow]
  [5],    // Cracow    -> [Warsaw]
  []      // There are no connections from Warsaw

If the graph is weighted, then each element in adjacency list is either a two element array or an object with vertex number and its weight.

Adjacency lists properties

  1. Space requirement is Teta(V+E).
  2. Edge lookup is O(d), where d is the degree of vertex (number of edges leaving the vertex).
  3. Retrieving all neighbors is O(1). Finding particular neighbor is O(N), where N is number of neighbors of V. You need to iterate through the list for the vertex V. It has max V-1 neighbors, so it is also O(V).
Share with the World!