Intro to Graph Data Structures

Data structures are just ways we organize data.

The one I'm sure you're familiar with is the list or array, a linear ordered sequence of values. This is your shopping list, your to-do, your reading, whatever.

Lets explore the way more exciting realm of non-linear graphs!

But first, some basics:

A graph is comprised of objects connected by lines.

In JavaScript (and computer science at large), we refer to those objects and lines as vertices and edges.

The benefit of a graph structure is that not only can you represent nodes of data but also their relationship to each other through properties assigned to their edges.

Two common properties of edges are weights and direction.

If a graph has weights, it is considered weighted and if it has direction, it is considered directed. Direction can go one way or both ways.

Susan can have a crush on Sally, but that doesn't mean Sally has a crush on Susan.

Now, imagine yourself, just floating in space all by your lonesome. You have a lot of knowledge, and no one to share it with.

Another space traveler appears, "Hey friend! Lets keep in contact". You give them your number, and suddenly, you have meaning and cease to be a singular speck of dust in space. You have become a node and you have created a connecting edge.

But it costs you.

Each time you call your space friend, you're billed by your telephone company $12393900.00. This is the weight of your connecting edge.

Lets come back from space and look at IRL graph data structures

Classic example is Google Maps. Its just one big graph!

Streets intersecting are vertices, and the streets themselves are edges.
They are weighted by distance in length and time. The streets also have a directionality property...some streets only go one way.

Traversing a Graph refers to finding a path between two nodes, finding the shortest path from one node to another and finding the shortest path that visits all nodes [1].

On of many methods to traverse a graph is using Dijkstra's algorithm (or Dijkstra's Shortest Path First algorithm, SPF algorithm). This is the one Google used (or a variant of) to implement their map application. This algorithm was originally conceived by Dijkstra in 1958 in 20 minutes at a cafe in Paris [2].

Here's what it looks like in Javascript:

A note on Tree Graphs...

That family tree you had to make in Kindergarten? Yup, a Tree Graph.

Here's the thing, Tree Graphs are a highly specialized form of a Graph, with a root node that all other nodes are decedents of.

Its important to make the distinction between a Tree Graph and a Graph, because they have some overlapping qualities like , but their rules on structuring data are completely different.

So in JavaScript, they are considered entirely different data structures.
For an in-depth and entertaining read on Trees, check out this article by fellow DEV community member Jill.

Graphs are a non-hierarchical structures of how data relates, connecting our entire world!

Title Image: Social Network Analysis Visualization [Grandjean, M. (2016)]
[1] https://www.jenniferbland.com/the-difference-between-a-tree-and-a-graph-data-structure/
[2]https://www.vice.com/en_us/article/4x3pp9/the-simple-elegant-algorithm-that-makes-google-maps-possible