Intro to Graph Data Structures in JavaScript
Believe it or not, you probably interact with at least a dozen graph data structures on a daily basis. Across the internet, graphs are one of the most widely used data structures by programmers and make some of your favorite features on the websites and apps you love possible. At the moment, it may seem like these structures are hidden in plain sight, but by the end of this article, you’ll be able to see how graphs are used to connect you to your closest friends on Facebook, find the highest rated restaurants in your area, or even get the fastest route to the coffee shop you love across town.
First, let's tackle how graphs are structured and built out in Javascript…
Whats a Graph and Real-World Implementations
Simply put a graph is a collection of nodes with edges between them. What does that mean? Here’s how that looks written out in Javascript:
[{edges:[B, C], data: 'hi'}, <--- A node
{edges: [A, C], data: 'hello'}, <--- B node
{edges: [A, B], data: 'hola'}] <--- C node
The graph data structure is simply an array that is holding objects, however in this case, each object will be referred to as a node. Each node holds an edge and data key/value pair.
The data key/value pair holds the value/information stored on that node and the edge key/value pair contains an array of references to other nodes. In the example above I’ve labeled each node at a specific index with a letter. Let’s take a closer look at the A node:
{edges: [B, C], value: 'hi}Looking at the A node’s edges we can see that it’s edges are the B and C node. I’ve condensed it a bit above, but if we were to look at the edges array for the A node more closely it would look like this:
[{edges: [A, C],value: 'hello'}, <--- B node
{edges: [A, B],value: 'hola'}] <--- C nodeAs you can see above, the edges nodes point to the B and C node objects. Edges are incredibly powerful because they enable connectivity among our nodes and ultimately help link the data we’re storing on our graph.
Let’s take a further look at some different types of graphs and how edges are implemented on each one.
Types of Graphs
There are a few different types of graph structures that are most commonly used in programming and each has different applications. Let’s take a look at some of them below:
Undirected → A graph with undirected edges that share a two-way relationship with one another
Directed → A graph with edges that are directed, these share a one-way relationship with one another
Weighted → If the edges in our graph have a value or costs assigned to them it’s weighed
Un-weighted → if the edges don’t have any value associated with them than the graph is unweighted and we can assume the weight is just 1
Real-World Applications
So it’s interesting to see how all of this works on the backend in Javascript, but what real-world implications to graphs hold?
One of the easiest examples to look at is social media. Take a look at the graph below:
Every connection you have to friends on Facebook, Twitter, Instagram, or any other social media network is referenced in some way on the backend in a graph. Looking at the above example, you can see the difference between graph structures represented by friendships on Instagram and Facebook.
On Instagram, you can follow a person, but that doesn’t necessarily mean they have to follow you back, which makes the graph connecting users with a directed graph. However, on Facebook, once a friend request has been accepted between two people they are now both following each other and will see each other's content on the website.
These types of connections are found all across the web! Next time, you’re browsing your favorite social media site, think about how users connect on the platform and what that means on the backend.
Conclusion
Now that you know what a graph is and how they work you’ll probably be able to point them out on a daily basis as you interact with your favorite sites on the web. Graphs are a powerful data structure used across many applications and websites, and there are many more we didn’t get a chance to explore!
If you’re interested in learning more about graphs and the different styles available, check out some of the resources I’ve shared below. Happy coding!
References for Images: