From Theory To Practice: Representing Graphs

Vaidehi Joshi
Sep 11, 2017 · 15 min read
From theory to practice: representing graphs

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 graph data structure: a (refresher of a) definition

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?)

Representing edges in directed vs. undirected graphs
The edge list as a way to represent a graph
[ 
[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!

An adjacency matrix: a defintion
Symmetry within adjacency matrices
Adjacency matrices: the good, the bad, the ugly
[
[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.

An adjacency list: a definition
An adjacency list is a hybrid between an edge list and an adjacency matrix
The practical points behind using adjacency lists
Space complexity of an adjacency list
An undirected graph, represented three ways
A directed graph, represented three ways

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.

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

basecs

Exploring the basics of computer science, every Monday, for a year.

Vaidehi Joshi

Written by

Writing words, writing code. Sometimes doing both at once.

basecs

basecs

Exploring the basics of computer science, every Monday, for a year.