Intro to Graph Data Structures
Tags: javascript, beginners, firstyearincode
Published: 2019-09-29 22:27:25


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. 

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/8d48c6klwattmg47q9t2.JPG) 



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  


![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/5sp8qepost3hny2k6pcx.JPG)
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: 

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/gidzjdndg2lstu5t8qnf.png)



####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] (https://dev.to/jillianntish/a-brief-descent-into-javascript-trees-48lm) 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