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.
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:
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.
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.
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.
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] , // Budapest -> [Cracow] , // 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).