At first glance understanding graphs can seem like a daunting concept (at least it was for me), but I’ve found graphs to be fascinating and incredibly relevant data structures. Once you learn about them it’s difficult to stop seeing the world as a collection and network of graphs. This article will attempt to remove some of the abstraction around graphs and dare I say it, make graph traversal fun. Let’s jump right in!
Prerequisites: Knowledge of Javascript, recursion, and a conceptual understanding of data structures are helpful — but don’t let that stop you!
First off, what is a graph?
In simple terms, you can think of a graph as a connected web of entities and their relationships. A family tree, a company org chart, your social network — all of these are real world examples of graphs representing the relationships between parents and their children, a company’s CEO and her employees, or your friends and friends of friends.
If you want to get a little more technical, a graph is a type of data structure that consists of vertices (entities), and edges (connections) that link the vertices together.
The diagram below represents a simple graph — the circles represent the entities, or vertices, while the lines that connect them are the edges.
When we think of graphs it’s important to understand the two main types:
- Directed vs. Undirected Graphs:
As the name implies, directed graphs signify a one-way relationship between entities. Think one-way flights or unrequited loves — love is going one way but it’s not coming back (ouch). On the other hand, when it comes to undirected graphs, love flows both ways.
Take Twitter for example. I may follow the Dalai Lama but unsurprisingly, His Holiness does not follow me back. This is an example of a directional, one-way relationship. On the other hand, I follow my dog and she follows me back because that’s what best friends do — here we have an example of an undirected relationship where we follow each other. We can illustrate these relationships using graphs below:
2. Weighted vs. Unweighted Graphs
Graphs may be weighted in which case the edges that connect our entities are given a value to represent something about that relationship. In an unweighted graph all edges are considered equal. Weighted graphs can be helpful if we’re trying to answer problems like finding the shortest distance between two points where our weights represent distances.
Why should we care about graphs?
Because they’re everywhere! Life is all about relationships. Think about your social network — your friends, family, colleagues, frenemies. You are connected to each one of those people in some way, and they too, are connected to their own networks who are then connected to their own networks and so on.
Graphs can help illustrate the world around us and educate real world decisions from the most basic to the extremely complex. How does Google maps find the most optimal route to your destination? How do social media networks like Facebook know how to recommend new friends you may know? How do airlines know how to optimize connecting flights?
Graphs! They’re everywhere and it’s highly likely that you interact with graphs every day. Just think about it for a minute and now I dare you to stop seeing the world in graphs.
What is graph traversal?
To better understand a graph or perform actions and make decisions based on a graph, we’ll need to understand graph traversal. Traversal is just a fancy way of saying ‘traveling’ through a graph and visiting vertices. There are many ways to do this, some better than others, but there’s no single answer, which makes the challenge of graph traversal so interesting!
So how do we do it?
Representing Graphs with Adjacency Lists
If we think about our graphs as a collection of vertices (entities) and edges (lines that connect them), we can think of graph traversal as a method of traveling along the edges to visit all of our vertices. In order to do that we need some way of storing information about our graph, more specifically we need a way to keep track of all the different ways we can travel to any given vertex.
We can do this using an Adjacency List. Let’s think of an adjacency list as a table that stores a vertex and its ‘neighbors’. Take a look at the graph below:
If we start at vertex A in this undirected graph, we have two possible paths — we can go to the right or the left. If we go right we land at B and if we go left we land at C. In essence, B and C are neighbors of vertex A, so let’s store that information in an adjacency list. We’ll use an object with key-value pairs where the keys represent potential starting vertices and the values represent their neighbors:
Graph: {
A: [ B, C ], (we'll use arrays to store neighbors)
B: [ A, D ],
C: [ A, D ],
D: [ B, C ]
}Great we now have an adjacency list that represents our graph! If we start at any given vertex, we can visit its neighbors and then visit its neighbor’s neighbors, and then its neighbor’s neighbor’s neighbors and so on and on and on until we’ve visited each vertex. Once we’ve reached the final vertex we’ve successfully traversed our graph!
Now that we have our method how do we represent it with Javascript?
Using Javascript and Recursion for Graph Traversal
We said above that we can start at any given vertex and visit its neighbors then repeat this process until there are no more vertices to visit. This sounds like we’re repeating the same steps over and over again which means we can use recursion to traverse through our graph.
If you’re not familiar with recursion, think of it as a way to break down a bigger problem into smaller, workable pieces where we can repeat the same action until we solve our bigger problem. Recursive solutions can be incredibly useful if we have a massive graph, or potentially don’t know the size of the graph we’re trying to traverse through.
So let’s pick a starting vertex and get to traversing. But we have a minor problem. How do we keep track of neighbors we’ve visited? If we don’t keep track of where we’ve been, we might revisit and annoy our old neighbors, or worse, get stuck in an endless loop.
As we traverse our graph let’s store ‘visited neighbors’ in another object and check to see if our vertex has already been visited. If it hasn’t, great, let’s explore its neighbors and store them in the visited neighbors list. If it has been visited then let’s not go down that route again but move on.
Here’s some pseudocode to get us started:
- Our goal is to print out all the vertices in our graph without repeat vertices
- As we traverse our graph we we’ll add our vertices to the ‘visited’ object and then check its neighbors to see if we’ve visited them already.
- If we’ve already visited a neighbor before, skip it and check its other neighbors.
- If we haven’t visited a neighbor before, we’ll repeat steps 2 and 3.
- Stop when we’ve visited all of our vertices
Show me the code!
Depth First Graph Traversal using recursion:
*Our graph will be our adjacency listconst graph = {
'A': [ 'B', 'C' ],
'B': [ 'A', 'D' ],
'C': [ 'A', 'D' ],
'D': [ 'B', 'C' ]
}function graphTraversal (vertex, graph) {
const allVertices = [] // this will be our 'result' array
const visitedVertices = {} // Let's use a helper function that we'll call on our vertices: function recursiveTraversal (vertex, graph) {
// An edge case just in case our vertex doesn't exist:
if (!vertex) return null // Mark the vertex as visited:
visitedVertices[vertex] = true
// Add the vertex to our result array:
allVertices.push(vertex)
// Loop over the vertex neighbors and repeat the process if we
haven't visited that neighbor before:
graph[vertex].forEach(neighbor => {
if (!visitedVertices[neighbor]) {
return recursiveTraversal (neighbor, graph)
}
})
}
// Call our recursive function:
recursiveTraversal(vertex, graph) return allVertices
}console.log(graphTraversal('A', test)) returns ['A', 'B', 'D', 'C']
This method of recursive traversal is also known as depth first traversal but we won’t go too much into that level of detail.
When conducting traversal we should also keep in mind the question — how ‘efficiently’ are we traversing? How much time does our traversal take and can we do better?
Big O of Graph Traversal
In our case of graph traversal, the Big O (fancy way of saying how much time and space your function takes up) time is O (|V + E|) where V represents that number of vertices in your graph and E represents the number of edges. We’ll save Big O for another article but the crux of it is that if our goal is to visit each node in our graph we would have to visit V number of vertices and E number of edges to check neighbors in order to make a successful round.
Let’s recap
We’ve covered a lot of ground so pat yourself on the back! We’ve learned that:
- Graphs are connected webs of entities and their relationships. These entities are also known as vertices and the connections are called edges.
- Graphs are everywhere in real life and they help us solve complex problems
- Graph traversal involves traveling through a graph and checking / visiting / doing something with each vertex
- We can represent graphs using adjacency lists and traverse through our graph using recursion. The Big O time of our method is O(|V + E|)
Parting is such sweet sorrow…
I hope this has been a fun introductory foray to graphs and graph traversal. If the code makes no sense don’t sweat it. I find it’s more valuable to understand the big picture conceptually first and the code (in your choice of language) will follow in time.
Thanks for reading and don’t blame me if you start seeing everything in graphs!
