Bare Bones Code: Representing Graphs

5 min readNov 24, 2018

Graphs have always been a tough topic for me to understand. In looking at resources it’s easy to get swamped by all the terminology associated with graphs and still not have any idea how to represent a graph in your code.

For this Bare Bones Code, I’ll show to represent a graph as an adjacency list and give a brief overview of the algorithms that are common for graphs.

How to Represent a Graph using ‘Nodes’:

For most graph problems (ones that don’t give you a grid/2d array), you want to use an adjacency list. That’s where each node has a list of the other nodes it has connections to.

Let’s jump into implementation. For representing a graph I use a Map (dictionary, associative array) where the key is the node, and the value is a list of nodes it is connected to. This is called an adjacency list.

You see on lines 6–8 that each node will have a list of nodes it is connected to.

So that’s a small example. In reality, most graph questions will use something else to represent nodes.

For example, if were an airline, we could make a graph where the cities are connected to other cities you can fly to.

Here’s an example:

And here is how it would look in code:

For cities that have no outgoing flights I just give them an empty list.

These are both examples of unweighted graphs.

With an unweighted graph you will usually do a depth-first search (DFS) or breadth-first search (BFS). This is what the code would look like for those:

Depth First Search — Using our graph structure

Breadth First Search — Using our graph structure

You’ll notice that to go from a depth-first search to a breadth-first search we only changed 1 line of code.

If we used our graph of cities, here is how the cities would be printed if we started at “Atlanta” for depth-first-search vs. breadth-first search:

Order of Depth First Search and Breadth First Search for our city example.

Time Complexity:

DFS: O(n) where n is the number of nodes in the graph because we go to each node.

BFS: O(n) where n is the number of nodes in the graph because we go to each node.

Space Complexity:

DFS: O(n) where n is the number of nodes in the graph because we are using additional data structures. Our set will end up storing all ’n’ nodes in our graph. And our toVisit stack will store every node at most once.

BFS: O(n) where n is the number of nodes in the graph. Our set will end up storing all ’n’ nodes in our graph. And our toVisit queue will store every node at most once.

There’s more to come for Graphs. There will be an article specifically about graph algorithms like DFS, BFS, and Dijkstra's, as well as another article about how to handle a graph when you’re given a 2d grid.

Representing a weighted graph:

Sometimes your graph will have weights, meaning that there is a cost associated with going from one node to another node.

Here is what our cities example would look like if we added costs:

We can still use our representation from earlier but we need to add a cost. To do that I use a Pair class. It stores the city and the cost to reach it. The class looks like this:

Example Pair class to store city and cost.

In other languages, you could probably use a tuple or an array with a string and an integer in it, but this is what I usually go with.

Here is how we would represent our graph now with costs:

The cities examples as a graph with costs.

This is a weighted graph. With a weighted graph, you usually perform Dijkstra’s algorithm, which means you are looking for lowest cost to reach a node from the start location.

At a high level Dijkstra’s algorithm is a BFS that uses a priority queue. With Dijkstra’s algorithm, you use a Priority Queue that’s ordered by how close a node is to the start.

Here’s how that would look:

Dijkstra’s algorithm on our cities example

With Dijkstra’s algorithm, you may visit a node in a graph more than once if there is a shorter path to reach it. You can also modify how your Priority Queue is ordered to changed how to traverse the graph. Here’s the order the graph is visited if we started at Atlanta:

Order of visiting cities using Dijkstra’s algorithm

Time Complexity and Space Complexity:

I’m still shaky on the time and space complexity of this algorithm so please refer to the Berkeley resource for a better overview of the runtime.

That’s it for representing graphs! There will be more articles to cover related topics. I plan to write an article specifically about depth-first-search, breadth-first-search, and Dijkstra’s algorithm. We also didn’t cover how to build a path by using these algorithms. Additionally, I’d like to cover when a grid is used to represent a graph.

Resources:

Here are the articles I pulled my information from for this post:

Bare Bones Code: Representing Graphs

Written by Jonathan Powell