# From Theory To Practice: Representing Graphs

Sep 11, 2017 · 15 min read

# An ordered pair by any other name

Since we’re already familiar with the theory behind graphs, 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.

The characteristics of graph are strongly tied to what its vertices and edges look 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 know?)

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

# When lists just won’t cut 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 is!

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

# Adjacency lists: the hybrid 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.

# 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 started.

2. Representing Graphs — Algorithms On Graphs, Coursera
3. Graph Representation — Adjacency List, mycodeschool
4. Graph Visualizations, VisuAlgo

Written by