**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).