From Theory To Practice: Representing Graphs
Tags: programming, tech, softwaredevelopment, datastructures
Published: 2017-09-23 22:10:14

---
title: "From Theory To Practice: Representing Graphs"
published: true
tags: programming,tech,software-development,data-structures
canonical_url: https://medium.com/basecs/from-theory-to-practice-representing-graphs-cfd782c5be38
cover_image: https://thepracticaldev.s3.amazonaws.com/i/3g8dxv2ij2rtul0ur7n8.png
description: The best investment you can make in your own learning is returning back to to the things you (think) you already know
---

The best investment you can make in your own learning is returning back to to the things you (think) you already know, and this is particularly true in the world of computer science. Everything in computing is a layer of abstraction built upon _even more layers_ of abstraction; if all the industries in the world were onions, computing would surely be one of the few with an uncountable number of&nbsp;layers.

All of these abstractions are also what makes software so hard (and sometimes, so intimidating). None of us know everything there is to know about how the software or hardware that powers our world works. And the truth of the matter is that none of us will ever really know all there is to know. But that’s okay! We learn what we need to learn at the moment, and we explore the new things that we are interested in exploring. Usually, this means learning more about things that we’re already at least a little bit acquainted with.

This is exactly why I love returning back to topics that I think I already know, and digging a little bit deeper under the surfaceâ€Š–â€Šyou will almost always find something new. Earlier in this series, we sunk our teeth into [the basics of graph theory](https://dev.to/vaidehijoshi/a-gentle-introduction-to-graph-theory); but there’s still so much more to know about graphs! We know that they are the foundations of fundamental things like social networks, or our even our browser histories, but how do they really work, and how do we implement them? We were gently introduced to the theory behind graphs, but how can we put that theory into practice and understand graphs on a deep level so that we can actually use them to solve real problems?

In order to do all of those things, we need to go back to the basics. We need to understand how to represent graphs and turn the theoretical into something more concrete.

### An ordered pair by any other&nbsp;name

Since we’re already familiar with [the theory behind graphs](https://dev.to/vaidehijoshi/a-gentle-introduction-to-graph-theory), we won’t dive too much into the history or applications of them here. The short version of the story is that graphs come from mathematics, and are nothing more than a way to formally represent a network, which is a collection of objects that are all interconnected.

In order to tackle the task of _representing_ a graph structure, which is so often present in computer science and across the web, we should make sure we’re comfortable with the parts of a graph, as well as its definition. A **_graph_** is a data structure with two distinct parts: a finite set of vertices, which are also called nodes, and a finite set of edges, which are references/links/pointers from one vertex to&nbsp;another.

![](https://cdn-images-1.medium.com/max/1024/1*AieKoYr68sm0GAFJUcNyDg.jpeg)<figcaption>The graph data structure: a (refresher of a) definition</figcaption>

A graph is defined by these two distinct parts, vertices and edges. Some graphs have many edges as compared to nodes, and are defined as **_dense_** graphs, whereas a graph a smaller edge-to-node ratio is called a **_sparse_** graph. Similarly, if the edges of a graph have a directional flow, the graph is defined to be **_directed_** , while a graph with edges that have _no_ directional flow is **_undirected_**.

> The characteristics of graph are strongly tied to what its vertices and edges look&nbsp;like.

Being able to identify these characteristics is very important since this directly affects how we go about representing a graph. But waitâ€Š–â€Šhow _do_ we represent a graph! That’s what we set out to do, but we haven’t actually gotten to that part yet, have we? Since we have some knowledge about graphs already, we can build upon that! (See what I meant about returning to topics that we _think_ we already&nbsp;know?)

We’ll recall that, in mathematics, graphs are represented as **_G = (V, E)_**, where _V_ is the set of vertices, and _E_ is the set of edges. When we learned about graph theory, we saw that there are two ways of representing this set of edgesâ€Š–â€Šeither as unordered pairs, or ordered pairsâ€Š–â€Šbased on whether the graph’s edges are directed or undirected.

Let’s quickly refresh what that means in practice.

![](https://cdn-images-1.medium.com/max/1024/1*J9U-CK1N6X7WBAnz_m04SQ.jpeg)<figcaption>Representing edges in directed vs. undirected graphs</figcaption>

In this example, we’ll see that the undirected graph’s edges, represented by _E_, have no order to them, since it’s possible to travel from one vertex to the other. However, in the edge set _E_ for the directed graph, there is directional flow that’s important to how the graph is structure, and therefore, the edge set is represented as ordered&nbsp;pairs.

This representation of a graph’s edges is the simplest possible way to represent a graphâ€Š–â€Šand we already kind of knew it! But how do these simple ordered pairs actually look in code and in memory? Well, that’s something we don’t know about yet (although we might be able to guess!). The answer is probably as easy as you expect it to be: the quickest way to turn this group of ordered pairs is to use a list or an array, depending on which language we’re&nbsp;using.

![](https://cdn-images-1.medium.com/max/1024/1*9uHj7ONZFgVwZ9OuD-kWbA.jpeg)<figcaption>The edge list as a way to represent aÂ graph</figcaption>

This list (or array) is called an **_edge list_** , and is a representation of all the edges (_|E|_) in the&nbsp;graph.

In the example shown here, we have a small graph, with just three nodes: 1, 2, and 3. Each edge is given an index, and represents a reference from one node to another. We’ll notice that there isn’t any particular order to the edges as they appear in the edge list, but every single edge must be represented.

For this particular graph, the edge list would look like&nbsp;this:

```
[ 
  [1, 2],
  [2, 3],
  [3, 1]
]
```

Because an edge list is really just an array, the only way to find something in this array is by iterating through it. For example, if we wanted to see if vertex 1 was connected to vertex 2, we’d need to iterate through this array and look for the existence of a pair [1, 2] or [2, 1]. Now, this is fine for our graph, which only has three vertices and three edges; iterating through this array isn’t really a big deal. But realistically speaking, most graphs are going to be _much_ bigger than this&nbsp;one!

Imagine having to iterate through a massive array to see if _one_ particular edge existed in the array; since the list of edges doesn’t have to follow any particular order, the edge could be at the very end of the list! Or, it could not be there at all, and we’d _still_ have to iterate through the whole thing to check for it. Not only would doing this work would take _linear_, **_O(E)_** time, where _E_ represents all the edges in the graphâ€Š–â€Šan edge list also requires _O(E)_ amount of space, and is yet fairly limiting in what we can do with it, despite needing that&nbsp;space.

Let’s remember what we started off with: this is the _simplest_ representation of a graph. Sometimes, the simplest version isn’t quite enough for us to work with. Some, let’s complicate it a little&nbsp;bit!

### When lists just won’t cut&nbsp;it

For most graphs, an edge list won’t end up being the most efficient choice. So, we can kick it up a notch and go from a list to a matrixâ€Š–â€Šan adjacency matrix, that&nbsp;is!

![](https://cdn-images-1.medium.com/max/1024/1*7xTtxr7I1Eq510-iDmxOsQ.jpeg)<figcaption>An adjacency matrix: a defintion</figcaption>

An **_adjacency matrix_** is a matrix representation of exactly _which_ nodes in a graph contain edges between them. The matrix is kind of like a lookup table: once we’ve determined the two nodes that we want to find an edge between, we look at the value at the intersection of those two nodes. The values in the adjacency matrix are like boolean flag indicators; they are either present or not present. If the value is 1, that means that there is an edge between the two nodes; if the value is 0, that means an edge does not exist between&nbsp;them.

Let’s look at an example to make this a little clearer. We’ll work with the same graph we used earlier, with just three nodes (1, 2, and 3)&nbsp;again.

![](https://cdn-images-1.medium.com/max/1024/1*bllOr7NiKf4YbNtqg1cEqA.jpeg)<figcaption>Symmetry within adjacency matrices</figcaption>

In this illustration, we can see that the adjacency matrix always has a main diagonal that will have a value of 0 down the diagonal, since most graphs that we’re dealing with won’t be referential. In other words, since node 2 cannot have a link to itself, if we draw a line from column 2 to row 2, the value will be 0. However, if we wanted to see if node 3 was connected to node 1, we could find column 3, row 1 and see that the value is 1, which means that there is indeed an edge between these two&nbsp;nodes.

The interesting thing about adjacency matrix representations of a graph is that, just by looking at them, we can tell whether the graph is _directed_ or _undirected_. We can determine this characteristic of a graph based on whether its adjacency matrix is _symmetric_ or not. If the values on both sides of the main diagonal of an adjacency matrix are the same, the matrix is **_symmetric._** In other words, if we looked up row x, column y, it would contain the same value as whatever was in row y, column x. If this was true for all the rows and columns of the matrix, the matrix would be symmetric, which our particular graph representation happens to&nbsp;be.

It will become more clear how the symmetry of a matrix is tied to the “directness” of a graph in the next&nbsp;section.

![](https://cdn-images-1.medium.com/max/1024/1*awItc9GQX4siLgQAlTQM7A.jpeg)<figcaption>Adjacency matrices: the good, the bad, theÂ ugly</figcaption>

Adjacency matrices are definitely a step up from an edge list, for sure. For one thing, they are fairly easy to represent; our adjacency matrix would be look like&nbsp;this:

```
[
  [0, 1, 1],
  [1, 0, 1],
  [1, 1, 0]  
]
```

Adding or deleting an edge, from a graph is also easy to do with this representation, since looking up a potential node between two edges only requires knowing the two nodes, finding the appropriate index for each, and finding the value at the intersection between the two. Most operations on an adjacency matrix can be done in _constant_, or **_O(1)_**&nbsp;time.

However, what would happen if we had a _sparse_ graph? What would our adjacency matrix look like if our graph had very few edges as compared to nodes? Well, we can probably imagine it without having to even draw it out: it would mostly be filled with values of 0. But, because of the way that a matrix is structured, we’d still need to build out the entire&nbsp;thing!

The trouble with adjacency matrices is that they will always require **_O(VÂ²)_** amount of space, which, depending on what our graph looks like, can mean a lot of wasted space! So, as great as an adjacency matrix can be, it isn’t always the right representation for a graph (particularly if that graph is&nbsp;sparse).

Well, not to worry. There’s yet another option when it comes to graph representationâ€Š–â€Šand it’s the most fun one of&nbsp;all!

### Adjacency lists: the hybrid&nbsp;choice

When both edge lists and adjacency matrices seem to fail us, what are we to do? Why, combine them both together, of course! And that’s exactly what an **_adjacency list_** isâ€Š–â€Ša hybrid between an _edge list_ and an _adjacency matrix_. An adjacency list is an array of linked lists that serves as a representation of a graph, but also makes it easy to see which other vertices are adjacent to _other_ vertices.

![](https://cdn-images-1.medium.com/max/1024/1*XrA9dYM744vLgDzvEohOKQ.jpeg)<figcaption>An adjacency list: a definition</figcaption>

An adjacency list is the most popular and commonly-used representation of a graph since most graph traversal problems (which we’ll see a whole lot more of, later on in this series!) require us being able to easily figure out which nodes are the neighbors of another node. In most graph traversal scenarios, we don’t even really need to _build_ the entire graph out; we just need to be able to know where we can travelâ€Š–â€Šin other words, who the neighbors of a node are. This is fairly easy to determine when using an adjacency list, since every single node/vertex has a reference to all of its neighbors through _an adjacent linked&nbsp;list_.

Let’s look an example to see what this looks like in practice.

![](https://cdn-images-1.medium.com/max/1024/1*XPH-Z7fBfBT1mEcN03FOJA.jpeg)<figcaption>An adjacency list is a hybrid between an edge list and an adjacency matrix</figcaption>

In the illustration drawn here, each vertex is given an index in its list, and has all of its neighboring vertices stored as an linked list (which could also be an array), adjacent to it. For example, the last element in the list is the vertex 3, which has pointer to a linked list of its neighbors. The linked list that is adjacent to vertex 3 contains references to two other vertices: 1 and 2, which are the two nodes that are connected to the node 3. Thus, just by looking up the node 3, we can determine who it’s neighbors are and, by proxy, quickly identify that it has two edges connected to&nbsp;it.

We can see that, because of the _structure_ of an adjacency list, it’s very easy to determine all the neighbors of one particular vertex. In fact, retrieving one node’s neighbors takes _constant_, **_O(1)_** time, since all we really need to do is find the index of the node we’re looking for, and pull out its list of adjacent vertices.

But what if we wanted to find a particular edgeâ€Š–â€Šor check whether an edge between two nodes exists? This was easy to do with an adjacency matrix…but how easy is it with an adjacency list?

![](https://cdn-images-1.medium.com/max/1024/1*ZSsASthwtg_2iQHsbSkXSw.jpeg)<figcaption>The practical points behind using adjacency lists</figcaption>

Well, to find a specific edgeâ€Š–â€Šfor example, (x, y)–we need to find vertex x in the adjacency list, which we already know takes constant, _O(1)_ time to look up as an index. The second step is checking to see whether y is in the adjacency list for node x. This could be fairly quick to do, particularly if y is first in the list, or if it’s the _only_ item in the&nbsp;list.

But, what about the worst-case scenario? Well, y could potentially be at the _very_ _end_ of the linked list. Or, it might not even exist! In that case, we’d end up iterating through the whole linked list to check for it, which will take us **_O(d)_** time, where _d_ is the degree of vertex x. The **_degree_** of a vertex is the number of edges that it has, which is also known as the number of neighboring nodes that it&nbsp;has.

![](https://cdn-images-1.medium.com/max/1024/1*-z8EtJ0BpjWs_ZnToj_wKQ.jpeg)<figcaption>Space complexity of an adjacency list</figcaption>

So, how big could our degree possibly end up being? Well, the maximum possible value for the degree (_d_) of any vertex in a graph can never be more than (|V|â€Š–â€Š1), where _V_ is the total number of vertices in the graph. If we think about it, this makes sense; the highest number of potential neighbors that node could ever have is _every single node_ in the graph, except for itself! The minimum possible value for _d_ is 0, since we could always have a graph that has only one vertex, which would mean that it has 0 edges and 0 neighboring nodes.

Okay, so now that we know how much time it could possibly take us to iterate through an adjacency list, what about how much space it takes&nbsp;up?

An adjacency list itself will require **_|V|_** amount of space for the list, since every single vertex is going to require it’s own index and spot in the list. The vertex will also need a pointer reference to its linked list/array of neighbors, but a pointer takes a negligible amount of space in memory. So what about the linked list itself? We have already determined that the longest that a linked list of neighboring nodes could ever possibly be is **_(|V|-1)_**, in the worst&nbsp;case.

But there’s one additional caveat here: the total number of elements for every single edge represented in an adjacency list depends on whether the graph is _directed_ or _undirected_.

This starts to become more obvious when we compare an undirected graph representation with a directed graph representation! So let’s take a look and see how they&nbsp;compare.

![](https://cdn-images-1.medium.com/max/1024/1*OuGzFyh22HxjzqLUyNsHDA.jpeg)<figcaption>An undirected graph, represented threeÂ ways</figcaption>

In this **_undirected_** graph example, we have five nodes, and eight undirected edges.

Since we know that there are three different ways to represent this graph, let’s look at all of these formats with this one example. The _edge list_ is the most straightforward of the three: it’s an array of the eight edges, which explains why its indices range from 0-7. If we look at the _adjacency matrix_ for this undirected graph, we’ll notice that it’s symmetric. Consider that every single node that is connected to a neighboring node in an undirected graph has its edge mirrored in it’s neighboring node; this is why an undirected graph will always have a symmetric adjacency matrix.

Now, to answer our final question: how does our _adjacency list_ change in size based on the directness of our graph? Well, if we look at this adjacency list example, we’ll notice that each edge appears twice. For example, vertex 2’s adjacency list contains a reference to vertex 5; similarly, vertex 5’s adjacency list contains a reference to vertex 2. Each edge is represented twice, so the total amount of elements that we will need to allocate space for in an adjacency list is actually **_2(|E|)_** elements, where _E_ is the total number of edges in an undirected graph.

![](https://cdn-images-1.medium.com/max/1024/1*wBqdISORWCjHLqf9qZ_N-A.jpeg)<figcaption>A directed graph, represented threeÂ ways</figcaption>

Now that we’ve looked at all three representations of an undirected graph, we might already be able to guess how a **_directed_** graph compares.

In this illustration, we have five nodes, and seven edges. The _edge list_ representation of this graph has, as we might expect, seven elements, with indices that range from 0-6, one for each of the directed&nbsp;edges.

We’ll notice that _adjacency matrix_ for a directed graph looks a little different from any that we’ve seen before! That’s because it is _not symmetric_. If we look up (0, 1), we’ll see that the value is 0, but if we look up (1, 0), we’ll see that the value is 1! This is because of the directional flow of the edges in this graph; not every node has a bi-directional link to a neighboring node, and the layout of the adjacency matrix displays that perfectly.

Finally, the _adjacency list_ representation of this directed graph also looks different from what we saw in undirected one earlier. We’ll notice that the list contains only **_|E|_** number of elements, where _E_ is the total number of edges. If we think about it a bit more, it makes sense; the edges aren’t bidirectional in this graph, so we don’t need to represent them twice for each node; rather, they are one-way connections between nodes, so we only need to represent them once, for whichever node is linked to its neighbor.

Thus, the representation of a graph (and how much space it takes up) all depends on what the graph looks like, and what we’re trying to do with! As is the case with most things in computer science, the answer to “which representation should we use?” is quite literally: _it depends on what you want to&nbsp;do!_

For the purposes of this series and understanding graph traversal algorithms and graph coloring problems, we’ll most likely be using adjacency lists. But, as always, they are just one tool for the job. The most important thing, howeverâ€Š–â€Šfar more important that what representation we choose to useâ€Š–â€Šis the fact that we _know_ how to transform theory into practice!

### Resources

Understanding the basics of the graph theory is pretty fundamental to unpacking some of the most complicated and well-known computer science problems. But knowing all that theory isn’t helpful if you can’t apply it! Thankfully, there are a lot of good resources that show how to represent a graph in programmatic terms. If you’re looking to understand even more, these are some good places to get&nbsp;started.

1. [Graph and its representations](http://www.geeksforgeeks.org/graph-and-its-representations/), Geeksforgeeks
2. [Representing graphs](https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs), Khan&nbsp;Academy
3. [Representing Graphsâ€Š–â€ŠAlgorithms On Graphs](https://www.coursera.org/learn/algorithms-on-graphs/lecture/c4W9f/representing-graphs),&nbsp;Coursera
4. [Graph Representationâ€Š–â€ŠAdjacency List](https://www.youtube.com/watch?v=k1wraWzqtvQ&t=2s), mycodeschool
5. [Graph Visualizations](https://visualgo.net/en/graphds), VisuAlgo

* * *


_This post was originally published on [medium.com](https://medium.com/basecs/from-theory-to-practice-representing-graphs-cfd782c5be38)_