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:
- Memory requirements – space needed to represent a graph.
- How fast can we determine whether an edge exists in the graph.
- How fast is to find neighbors of a vertex.
Let’s consider the following rail map as graph:
- Barcelona has direct train to Berlin.
- Berlin has direct train to Warsaw.
- Berlin has direct train to Cracow.
- Barcelona has direct train to Budapest.
- Budapest has direct train to Cracow.
- Cracow has direct train to Warsaw.
Our enumerated cities/nodes/vertices are:
- Barcelona.
- Berlin.
- Budapest.
- Cracow.
- 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
- Space requirement is Teta(E).
- 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).
- 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
- Space requirement is Teta(VxV).
- Edge lookup is in constant time – O(1).
- 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
- Space requirement is Teta(V+E).
- Edge lookup is O(d), where d is the degree of vertex (number of edges leaving the vertex).
- 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).
